Find a fixed point (value equal to index)
Problem
Given a sorted array of distinct integers, return an index i with arr[i] === i, or −1 if there is none.
Example 1
Input: [-10, -5, 0, 3, 7] Output: 3
Example 2
Input: [-10, -5, 3, 4, 7, 9] Output: -1
Also asked as: Find a Fixed Point (Value equal to index) in a given array
Test cases
Case 1
Input: [-10,-5,0,3,7] Expected: 3
Case 2
Input: [-10,-5,3,4,7,9] Expected: -1
Case 3
Input: [0] Expected: 0
Case 4
Input: [1,2,3] Expected: -1
View solutionHide solution1 approach
1. Binary search (distinct sorted array)
Time O(log n)Space O(1)
If a[mid] === mid you are done. If a[mid] < mid the fixed point can only be on the right, else on the left.
function fixedPoint(a) { let lo = 0, hi = a.length - 1; while (lo <= hi) { const mid = (lo + hi) >> 1; if (a[mid] === mid) return mid; a[mid] < mid ? (lo = mid + 1) : (hi = mid - 1); } return -1;}