Algorithm · Microsoft · Hard
Consider an integer array A arranged in non-decreasing order. Its length n is unknown. The only permitted access is an API method get(i); for a nonnegative index i, it returns A[i] when $$0 \le i = target. Since out-of-range probes return $$+\infty$$, this loop always finishes. Then run binary search inside the bracket to find the first index satisfying the condition. The entire algorithm must take $$O(\log n)$$ time and make $$O(\log n)$$ calls to get. Your solution must…
Checking your access…