Leetcode1064 Fixed Point

Description

Given an array A of distinct integers sorted in ascending order, return the smallest index i that satisfies A[i] == i. Return -1 if no such i exists.

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

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

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

Note: 1 <= A.length < 10^4 -10^9 <= A[i] <= 10^9

Solution

Use binary search. There is one assumption: no duplication. We can put this problem to first kind question of our binary search problem set.

Code

class Solution {
public:
    int fixedPoint(vector<int>& A) {
        int left = 0;
        int right = A.size()-1;
        
        while(left <= right) {
            int mid = left + (right-left)/2;
            if(A[mid] == mid){             /*❶*/
                return mid;
            } else if(A[mid] > mid){       /*❶*/
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
};

❶ As you can see, this is the only place changed in binary search template describe in this thread.

Insight

Review binary search template again.