Problem statement

https://leetcode.com/problems/fixed-point/

Solution

One way is to use linear search.

There is better solution with binary search: we need to check the place where A[x] - x == 0. Notice, that A[x] - x sequence is non-decreasing. If we have A[mid] - mid < 0, it means that we can not use the left half with mid including, so we put beg = mid + 1, in the opposite case put end = mid.

Complexity

Time complexity is O(log n), space is O(1).

Code

class Solution:
    def fixedPoint(self, A):
        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