Fixed Point

easy binary search array

Problem

Given an array of distinct integers arr sorted in ascending order, return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.

Inputarr = [-10, -5, 0, 3, 7]

Output3

For i = 3, arr[3] == 3, so the answer is 3.

arr (sorted, distinct, comma-separated)

def fixed_point(arr):
    lo, hi = 0, len(arr) - 1
    ans = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] >= mid:
            if arr[mid] == mid:
                ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

function fixedPoint(arr) {
  let lo = 0, hi = arr.length - 1, ans = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] >= mid) {
      if (arr[mid] === mid) ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return ans;
}

class Solution {
    public int fixedPoint(int[] arr) {
        int lo = 0, hi = arr.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] >= mid) {
                if (arr[mid] == mid) ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }
}

int fixedPoint(vector<int>& arr) {
    int lo = 0, hi = (int)arr.size() - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] >= mid) {
            if (arr[mid] == mid) ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return ans;
}

Explanation

A fixed point is an index i where arr[i] == i, and we want the smallest such index. Because the array has distinct values sorted ascending, the difference arr[i] - i never decreases, which lets us binary-search instead of scanning.

At each step we compare arr[mid] with its index mid. If arr[mid] < mid, values are lagging behind their indices, so any fixed point must be to the right — set lo = mid + 1. If arr[mid] >= mid, a fixed point can only be at mid or to the left, so we move hi = mid - 1, and when it is an exact match we record ans = mid before continuing left to look for an even smaller one.

This "record and keep going left" trick is what guarantees we end up with the smallest qualifying index rather than just any one.

Example: arr = [-10,-5,0,3,7]. The negatives lag their indices, pushing us right; at mid = 3 we find arr[3] == 3, record ans = 3, and a final check left confirms nothing smaller works, so the answer is 3.

If no index ever matches, ans stays -1. The whole search is O(log n).

Time: O(log n) Space: O(1)