Question

Formatted question description: https://leetcode.ca/all/1064.html

 1064. Fixed Point

 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

Algorithm

The basic idea of binary search is to divide n elements into two roughly equal parts, and compare a[n/2] with x.

If x=a[n/2], then find x and the algorithm stops;
if x<a[n/2], as long as you continue to search for x in the left half of array a,
if x>a[n/2], then as long as you search for x in the right half of array a.

Code

public class Fixed_Point {

    // binary search, logN
    class Solution {
        public int fixedPoint(int[] A) {
            //Run binary search
            int lo = 0;
            int hi = A.length - 1;

            while (lo <= hi){
                int mi = lo + (hi - lo) / 2;
                if (A[mi] == mi) return mi;
                if (mi < A[mi]) hi = mi - 1;
                else lo = mi+1;
            }

            return -1;
        }
    }


    class Solution_bruteForce {
        public int fixedPoint(int[] A) {
            for (int i = 0; i < A.length; i++) {
                if (A[i] == i) {
                    return i;
                }
            }
            return -1;
        }
    }

}

// OJ: https://leetcode.com/problems/fixed-point/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int fixedPoint(vector<int>& A) {
        int N = A.size(), L = 0, R = N - 1;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] < M) L = M + 1;
            else R = M - 1;
        }
        return L < N && A[L] == L ? L : -1;
    }
};

class Solution:
    def fixedPoint(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1
        while left < right:
            mid = (left + right) >> 1
            if arr[mid] >= mid:
                right = mid
            else:
                left = mid + 1
        return left if arr[left] == left else -1

func fixedPoint(arr []int) int {
	left, right := 0, len(arr)-1
	for left < right {
		mid := (left + right) >> 1
		if arr[mid] >= mid {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if arr[left] == left {
		return left
	}
	return -1
}

function fixedPoint(arr: number[]): number {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (arr[mid] >= mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return arr[left] === left ? left : -1;
}

1064 - Fixed Point

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions