I'm given an n sized array that houses a max-heap in it's first x elements (x is unknown). After those x elements, each element has value of infinity. My task is to find x in log(x) time complexity. For example, if n=2^100 and x happens to be equal to 30, then I need to perform 5 operations, and not 100.
So far the only method I thought of was to go down the heap (either only to left sons or right sons) until I go out of bounds or reach a node whose next child's value is infinity, Afterwards I would go linearly from the current node till I find x.
However the linear progression I performed is of O(x) time complexity and thus this method yields O(x).
Maybe I didn't search hard enough, but I haven't seen solutions to this online yet. Any help would be really appreciated.
Keep doubling the index you check until you get to the first infinity. Say this happens at index 2^k.
I.e., check indices in this order: 0, 1, 2, 4, 8, 16, 32, ..., 2^(k-1), 2^k. We stop at 2^k because arr[2^k] == infinity.
Then we do binary search between 2^(k-1) and 2^k to find the index x.
This has O(log x) complexity.