1064.md

1064. Fixed Point

Level:

Topic:

Question

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.

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.

Intuition

Binary Search

[-10,-5,0,3,7]
   0, 1,2,3,4

• if index <= num, search in the left side
  • because it should return the smallest index i, even if it equals, it looking for the smallest
• else, search in the right size
• if found, fulfill this condition index = num then return the index
• else, return -1

Code

Time: O(log n)
Space: O(1)

public int fixedPoint(int[] arr) {
    int low = 0, high = arr.length-1;

    while (low < high) {
        int mid = low + (high-low)/2;

        if (mid <= arr[mid])
            high = mid;
        else
            low = mid+1;
    }

    if (low == arr[low])
        return low;

    return -1;
}