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.

Ugh, I'm an idiot. I removed "fixed" for it to be easier to read just for this post. Otherwise, this typo is not found in my original code. I have been at this for hours. I'll fix that — n3vdawg
– n3vdawg, Commented Jun 3, 2018 at 1:46
The mid that you're looking for is the midpoint with respect to the original array, right? When you slice the list and pass it in for the next call, the size changes so none of your if conditions are going to hold true after, because the mid you're looking for, and the mid you end up comparing will not be the same. — cs95
– cs95, Commented Jun 3, 2018 at 1:47
By the way, my understanding of "fixed point" is that the index of a value is equal to the value... right? — cs95
– cs95, Commented Jun 3, 2018 at 1:48
Hm, that makes sense. I guess I need to think about how I could fix that.... — n3vdawg
– n3vdawg, Commented Jun 3, 2018 at 1:48
Yes, the index of a value needs to be equal to its value @coldspeed — n3vdawg
– n3vdawg, Commented Jun 3, 2018 at 1:49

cs95 · Accepted Answer · 2018-06-03 01:53:32Z

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.

answered Jun 3, 2018 at 1:53

cs95

406k106 gold badges744 silver badges797 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

n3vdawg Over a year ago

Wow, this makes so much more sense. What was I thinking.... Thank you for your help.

John Zwinck · Accepted Answer · 2018-06-03 01:53:15Z

0

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].

answered Jun 3, 2018 at 1:53

John Zwinck

252k44 gold badges346 silver badges459 bronze badges

1 Comment

n3vdawg Over a year ago

Can't believe I would overlook something like that. I really appreciate the clarification on how I was wrong in my approach. Thank you.

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related