我得到一个 n 大小的数组，它的前 x 个元素中包含一个最大堆（x 未知）。在这些 x 元素之后，每个元素的值为无穷大。我的任务是在 log(x) 时间复杂度中找到 x。 例如，如果 n=2^100 并且 x 恰好等于 30，那么我需要执行 5 次操作，而不是 100 次。
到目前为止，我想到的唯一方法是沿着堆向下移动（要么只到左儿子，要么只到右儿子），直到出界或到达下一个子节点的值为无穷大的节点， 然后我会从当前节点开始线性移动，直到找到 x。
然而，我执行的线性级数的时间复杂度为 O(x)，因此该方法产生 O(x)。
也许我搜索得不够努力，但我还没有在网上看到这个问题的解决方案。任何帮助将非常感激。
继续将检查的索引加倍，直到到达第一个无穷大。假设这发生在索引 2^k 处。
即，按以下顺序检查索引：0, 1, 2, 4, 8, 16, 32, ..., 2^(k-1), 2^k。我们停在 2^k 处，因为 arr[2^k] == 无穷大。
然后我们在 2^(k-1) 和 2^k 之间进行二分查找以找到索引 x。
其复杂度为 O(log x)。