Skip to interview prep
Apexed

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]).

In a sorted array of distinct integers, how do you find an index i with A[i] = i — Data structures & algorithms interview question — Apexed