430. Find Fixed Point (arr[i] == i) in Sorted Array

Given a sorted array of distinct integers arr, return the smallest index i such that arr[i] == i. Return -1 if no such index exists. Solve in O(log n).

Input: A sorted array of distinct integers arr (0-indexed).

Output: Smallest index i where arr[i]==i, or -1.

Examples

Input: [-10,-5,0,3,7]
Output: 3
Explanation: arr[3]=3. Check: arr[0]=-10≠0, arr[1]=-5≠1, arr[2]=0≠2, arr[3]=3==3.

Input: [0,1,2,3,4]
Output: 0
Explanation: arr[0]=0, which is the smallest (first) fixed point.

Input: [1,2,3,4,5]
Output: -1
Explanation: No index i where arr[i]==i. Return -1.

Constraints

• 1 <= arr.length <= 10^4
• All elements distinct
• Sorted ascending
• -10^6 <= arr[i] <= 10^6

Asked by