Find a fixed point (value equal to index)

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}