Find a Fixed Point (Value equal to index) in a given array

In a sorted row of different numbers, find a box whose number is the same as its own position.

Simple way: time O(n)
room O(1)
Clever way: time O(log n)
room O(1)

The problem, simply

You get an array of different whole numbers sorted from small to big. Positions start at 0. A fixed point is a position i where arr[i] == i: the box holds its own position number.

Return such a position. If there is none, return -1.

A story to remember it

Picture it

arrayvalues (index under each box)

arrayvalue minus index (never goes down)

Only box 3 holds its own index. The second row is value minus index. It never goes down, so the 0 we want sits where the row crosses from negative to positive.

answer

Examples

A normal case

In: [-10, -1, 0, 3, 10, 11, 30, 50, 100]
Out: 3

arr[3] is 3.

At the very start

In: [0, 2, 5, 8, 17]
Out: 0

arr[0] is 0.

At the very end

In: [-1, 0, 1, 2, 3, 5]
Out: 5

Every box is one behind its index until the last one, which catches up.

No fixed point

In: [-10, -5, 3, 4, 7, 9]
Out: -1

Boxes 0 and 1 are behind, and from box 2 on every box is ahead. Nothing matches.

One box

In: [0]
Out: 0

The single box holds 0 at index 0.

Way 1: the simple way

Check every box from left to right. Return the first index where the value equals the index.

java

class Solution {
    public int fixedPoint(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == i) return i;   // the box holds its own index
        }
        return -1;
    }
}

How long it takes: one look at each box, O(n). Extra room: O(1). This works on any array, sorted or not.

Way 2: the clever way

Because the numbers are sorted and all different, arr[i] - i never goes down from left to right. A fixed point is a place where it is exactly 0. So binary search for 0 in that hidden row, without ever building it.

lo = 0, hi = n - 1.
Look at the middle box mid.
If arr[mid] == mid, return mid.
If arr[mid] < mid, every box to its left is also behind. Search right: lo = mid + 1.
If arr[mid] > mid, every box to its right is also ahead. Search left: hi = mid - 1.
If lo passes hi, return -1.

Peek in the middle, drop the half that cannot match

01 / 08

arrayvalues (index under each box)

arrayvalue minus index (never goes down)

We want a box whose value equals its own index. lo is 0 and hi is 8. The second row shows value minus index; we want a 0 there.

checking
answer
rejected

java

class Solution {
    public int fixedPoint(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == mid) return mid;
            if (arr[mid] < mid) lo = mid + 1;   // behind, and so is everything on the left
            else hi = mid - 1;                  // ahead, and so is everything on the right
        }
        return -1;
    }
}

How long it takes: the range halves each time, O(log n). Extra room: O(1).

Watch out for

If there can be several fixed points, this code returns any one of them. To get the smallest, record mid and keep searching left.
Unsorted input: binary search gives wrong answers. Fall back to Way 1.
Check the problem's indexing. Some versions count positions from 1, so the test is arr[i] == i + 1.

What interviewers ask next

Smallest fixed point? When arr[mid] == mid, save it and set hi = mid - 1.
What if values repeat? Search both sides, but skip smartly: on the left, only up to min(mid - 1, arr[mid]), and on the right, only from max(mid + 1, arr[mid]). It is O(n) in the worst case but often much faster.
The GeeksforGeeks practice version is unsorted, counts from 1, and asks for all matches. Then you must scan, O(n).
Why does "never goes down" hold? arr[i + 1] >= arr[i] + 1 because the numbers are whole and different, so arr[i + 1] - (i + 1) >= arr[i] - i.

Remember this

Grown-up words: the box that holds its own index is a fixed point (also called a magic index), and the hidden row arr[i] - i is a monotonic (non-decreasing) sequence, which is what makes binary search possible.