339. Find a Fixed Point in an Array

Given a sorted array of n distinct integers (which may include negative numbers), find an index i such that arr[i] == i - a 'fixed point'. If more than one such index exists, print the smallest one. If none exists, print -1.

Input: The first line contains an integer n. The second line contains n space-separated sorted, distinct integers, which may include negative numbers. Output: Print the smallest index i such that arr[i] == i, or -1 if no such index exists.

1 <= n <= 10^5

Finding the SMALLEST fixed point (when multiple exist) requires the same 'keep searching one direction after a match' refinement seen in 'Find First and Last Position' - a recurring binary-search-variant technique worth recognizing across problems.

In a sorted array, find an index where the value stored there equals the index itself. Brute force: Scan the array linearly checking arr[i]==i for every index - this costs O(n), unnecessary given the array's sorted, strictly-increasing structure enabling a much faster search. Optimised: The strictly increasing, sorted nature of the array guarantees (arr[i] - i) only ever increases or stays flat as i grows - this monotonic property lets binary search directly narrow down to a fixed point (and, with the 'keep searching left after a match' refinement, the SMALLEST one) in O(log n).

Since the array holds strictly increasing distinct integers, the sequence arr[i] - i is non-decreasing as i increases, so binary search on this quantity to find any single index where arr[mid] equals mid (steering left when arr[mid] - mid > 0 and right when it is negative). Once any fixed point is found, walk backward from it, decrementing while the previous index is still a fixed point, to find the smallest one, since consecutive fixed points can form a run. This finds a fixed point in logarithmic time, a real improvement over scanning from the start, but the backward walk after finding one can still cost linear time if a large contiguous run of fixed points exists. Time: O(log n + k) where k is the run length of fixed points Space: O(1)

Rather than finding any fixed point and then backtracking, binary search directly for the leftmost index where arr[i] - i is greater than or equal to zero, using the fact that this quantity is non-decreasing across the whole array. Because of that monotonicity, this leftmost boundary is guaranteed to be the smallest fixed point if arr[i] actually equals i there, or proof that no fixed point exists otherwise. This needs only a single binary search with no backward scanning step afterward, giving a worst case that stays logarithmic no matter how many fixed points the array contains. Time: O(log n) Space: O(1)

Scan the array from left to right and check at each index i whether arr[i] equals i, returning the first index where this holds, or -1 if none is ever found. This is a direct check of the definition and is trivially correct, but it does not use the fact that the array is sorted, so it may need to examine every element. Time: O(n) Space: O(1)

1. Notice that since the array is strictly increasing with integer values, the expression (arr[i] - i) is non-decreasing as i increases - this monotonic behavior enables binary search. 2. At a candidate mid: if arr[mid] < mid, any fixed point must be to the RIGHT; if arr[mid] > mid, it must be to the LEFT; if arr[mid] == mid, it's a valid candidate, but keep searching LEFT for an even smaller matching index. 3. Track the smallest matching index found.

Time: O(log n) - a modified binary search. Space: O(1) - just a few pointer variables.

Test n = 1, an array with no fixed point (-1), an array with multiple fixed points (print the smallest index), and n = 10^5 for performance.

Be ready to explain the monotonicity argument clearly (why arr[i]-i is non-decreasing) - this justification is what makes binary search valid here, rather than it just being a lucky coincidence.