351. In a sorted array of distinct integers, how do you find an index i with A[i] = i?
MediumDivide & conquer
Technical
Show model answer
Because elements are distinct integers and sorted, A[i + 1] ≥ A[i] + 1, so B[i] = A[i] − i is non-decreasing. Binary search for B[i] = 0: if A[mid] < mid, every index to the left also has A[j] < j, so search right; if A[mid] > mid, search left. This is O(log n) time and O(1) space, compared with the O(n) linear scan.
With duplicates the monotonic property breaks, and in the worst case you may need O(n). A practical improvement still prunes: after checking mid, search the left part only up to min(mid − 1, A[mid]) and the right part only from max(mid + 1, A[mid]).