Find a fixed point with only one input (an array) for the function

Question

I am trying to find a fixed point in an array using a function that only accepts one input (an array). The problem is, I'm trying to avoid building another function that this function can call. If I could do that, this situation would be solved. These arrays will contain a list of sorted integers for me to iterate through. I am trying to keep its runtime low by using binary search. I've tried this a 100 different ways, and nothing is quite working.

def fixed_point(a):    

    if len(a) <= 2: # tried len(a) == 0 and len(a) == 1
        return -1 

    mid = len(a)//2 # have used (len(a)-1)//2 as well

    if mid == a[mid]:
        return a[mid]

    if mid > a[mid]:
        return find_point(a[mid+1:])

    else:
        return find_point(a[:mid])

    return -1

This function will return -1 if no fixed point is found.

This function also passes 10000 tests built for this, but for some reason cannot find that "5" is the fixed point of array: [-10, -5, -2, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129]

Curious as to what people might find wrong with this code.

Answer 1

To repeat what I said in my comment, the problem is that you're losing track of a.

Your approach is recursive, and you pass a list with shrinking size at each call. Because of this, the mid you're looking for, and the mid you end up comparing aren't the same.

Switch to an iterative approach, and you can keep things within the context of the original a.

def fixed_point(a):
    l, u = 0, len(a)

    while l <= u:
        m = (l + u) // 2
        if m == a[m]:
            return m
        elif m > a[m]:
            l = m + 1
        else:
            u = m - 1

    return -1

>>> fixed_point([-10, -5, -2, 2, 3, 5, 7, 10, 15, 25, 35, 78, 129])
5

Iteration also has the benefit of having lesser overhead in terms of memory (no need for call stacks), although on other languages, some compilers will optimise.

Answer 2

The fundamental problem with your algorithm as written is that you lose track of where you are in the original array. When you recurse, you return the fixed point of half of the array, but for example in [-4, -2, 0, 2, 4] when you split the array and find the fixed point in [2, 4] it doesn't work, because there is no fixed point in [2, 4]. You need to pass an offset into each recursive call, so you can say something like if mid + offset == a[mid].