Find a Fixed Point

Find a Fixed Point asks for an index that equals its own value in a sorted array. The naive scan is easy, but the sorted structure hides a logarithmic shortcut — the same binary search move you already know, with a clever twist on what you compare.

The slow way first

The obvious idea: walk the array and check every index. If a[i] == i, return i. That works and is only a few lines, but it is O(n) — it ignores the fact that the array is sorted.

The question to ask: can the sorted order tell me which direction the answer is in? If at some index a[mid] is already bigger than mid, can a fixed point still be to the right? With distinct sorted values, the answer is no — and that is exactly the hook for binary search.

The idea: binary search on a[mid] vs mid

Define diff(i) = a[i] - i. Because the array is sorted and the integers are distinct, each step right raises a[i] by at least 1 while i rises by exactly 1, so diff never decreases. A fixed point is just where diff(i) == 0.

That monotonic diff is all binary search needs. Look at the middle: if a[mid] == mid we are done. If a[mid] < mid then diff is negative here, so any zero must be to the right — set lo = mid + 1. Otherwise a[mid] > mid, diff is positive, and the zero must be to the left — set hi = mid - 1.

The key insight: we are not searching for a target value, we are searching for the spot where the value catches up to its index. Same skeleton as plain binary search, different comparison.

Walk through it

Step through the animation on [-10, -5, 0, 3, 7]. The pointers lo and hi mark the part still worth searching, and mid sits in the middle. First mid = 2, where a[2] = 0 < 2, so the whole left half is discarded. Next mid = 3, where a[3] = 3 — the value finally equals the index, and we return 3.

Pseudocode

lo, hi = 0, last index
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == mid:
        return mid                 # found a fixed point
    else if a[mid] < mid:
        lo = mid + 1               # value below index -> answer is to the right
    else:
        hi = mid - 1               # value above index -> answer is to the left
return -1                          # no fixed point exists

The Python solution

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

• lo and hi bracket the index range that could still hold a fixed point.
• mid = (lo + hi) // 2 is the midpoint; we compare a[mid] to mid itself, not to a target value.
• Line 5 is the win condition — a[mid] == mid means the value equals its index, so mid is a fixed point.
• a[mid] < mid: the value lags behind its index, and since diff never decreases, the zero is to the right, so lo = mid + 1.
• else (a[mid] > mid): the value is ahead of its index, so the zero is to the left, and hi = mid - 1.
• If the loop drains the range without a hit, no fixed point exists and we return -1.

Complexity

Binary search turns the linear scan into a logarithmic one and uses only a couple of pointers, so the extra space is O(1). The whole trick rests on the array being sorted with distinct values — that is what makes a[mid] - mid monotonic.

When this pattern shows up

Practice