Problem statement

https://binarysearch.com/problems/Fixed-Point/

Solution

Equal to Leetcode 1064 Fixed Point.

Complexity

It is O(log n) for time and O(1) for space.

Code

class Solution:
    def solve(self, A):
        if not A: return -1
        beg, end = 0, len(A) - 1
        
        while beg < end:
            mid = (beg + end) // 2
            if A[mid] - mid < 0:
                beg = mid + 1
            else:
                end = mid
        return beg if A[beg] == beg else -1