Problem

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

Examples

Example 1:

1
2
3

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

Example 2:

1
2
3

Input: arr = [0,2,5,8,17]
Output: 0
Explanation: arr[0] = 0, thus the output is 0.

Example 3:

1
2
3

Input: arr = [-10,-5,3,4,7,9]
Output: -1
Explanation: There is no such i that arr[i] == i, thus the output is -1.

Constraints:

  • 1 <= arr.length < 10^4
  • -109 <= arr[i] <= 10^9

Follow up: The O(n) solution is very straightforward. Can we do better?

Solution

Method 1 - Linear Search

Naive approach is to do the linear scan and find the magic index in O(n).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int findMagicIndex(int[] nums) {
	for (i = 0; i < nums.length; i++) {
		if (nums[i] == i) {
			return i;
		}

	}

	return -1;
}

Method 2 - Recursive Binary Search

Algorithm

  1. Check the middle element (mid = (start + end) / 2) and compares it to its index in nums[mid]. If they are equal (nums[mid] == mid), return mid as fixed point.
  2. If the middle element is greater than its index search the fixed point in the right half of array
  3. Conversely, if the middle element is less than its index search the fixed point might be in the left half

Why binary search works

Lets analyze case in point 2 in algorithm when mid > nums[mid].

We know the array nums is sorted and the function f(x) is increasing (meaning f(x) > f(y) for x > y).

When mid > nums[mid] , for eg. mid = 4, nums[mid] = 3… searching in left subarray will be useless, because mid will always be more than nums[mid] as elements are distinct. So, we just go to right subarray.

Similarly, when mid < nums[mid], for eg. mid = 4, nums[2] = 6, searching in right subarray will be useless, as mid will never be able to catch up with the nums[i] values. So, we can only go to left subarray.

Because of choosing just 1 path to find the answer, binary search.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int findMagicIndex(int[] nums) {
	return helper(nums, start, end);
}

private int helper(int[] nums, int start, int end) {
	if (start <= end) {
		int mid = (start + end) / 2;

		if (mid == nums[mid]) {
			return mid;
		}
		// mid > nums[mid] implies fixed point may be on right
		if (mid > nums[mid]) {
			return search(nums, mid + 1, end);
		} else { 
			return search(nums, start, mid - 1);
		}
	}

	return -1;
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Method 3 – Iterative Binary Search

Intuition

Since the array is sorted and all elements are distinct, we can use binary search to efficiently find the smallest index i such that arr[i] == i.

Approach

  1. Initialize left and right pointers for the array.
  2. While left <= right: - Compute mid = (left + right) // 2. - If arr[mid] < mid, search right half (left = mid + 1). - If arr[mid] > mid, search left half (right = mid - 1). - If arr[mid] == mid, record mid as a candidate and continue searching left half for a smaller index.
  3. Return the smallest index found, or -1 if none exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int fixedPoint(vector<int>& arr) {
        int l = 0, r = arr.size() - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == m) {
                ans = m;
                r = m - 1;
            } else if (arr[m] < m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func fixedPoint(arr []int) int {
    l, r, ans := 0, len(arr)-1, -1
    for l <= r {
        m := (l + r) / 2
        if arr[m] == m {
            ans = m
            r = m - 1
        } else if arr[m] < m {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int fixedPoint(int[] arr) {
        int l = 0, r = arr.length - 1, ans = -1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == m) {
                ans = m;
                r = m - 1;
            } else if (arr[m] < m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun fixedPoint(arr: IntArray): Int {
        var l = 0
        var r = arr.size - 1
        var ans = -1
        while (l <= r) {
            val m = (l + r) / 2
            if (arr[m] == m) {
                ans = m
                r = m - 1
            } else if (arr[m] < m) {
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def fixedPoint(self, arr: list[int]) -> int:
        l, r, ans = 0, len(arr) - 1, -1
        while l <= r:
            m = (l + r) // 2
            if arr[m] == m:
                ans = m
                r = m - 1
            elif arr[m] < m:
                l = m + 1
            else:
                r = m - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn fixed_point(arr: Vec<i32>) -> i32 {
        let (mut l, mut r, mut ans) = (0, arr.len() as i32 - 1, -1);
        while l <= r {
            let m = (l + r) / 2;
            let m_usize = m as usize;
            if arr[m_usize] == m {
                ans = m;
                r = m - 1;
            } else if arr[m_usize] < m {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fixedPoint(arr: number[]): number {
        let l = 0, r = arr.length - 1, ans = -1;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            if (arr[m] === m) {
                ans = m;
                r = m - 1;
            } else if (arr[m] < m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log n), since we use binary search on the array.
  • 🧺 Space complexity: O(1), as we use only a few variables.