Why does binary search algorithm not work?

Question

I've copied code from the book "grokking algorithms" for finding an item in the list using the binary search algorithm. The code launches great and returns no errors. However, sometimes it just doesn't work for certain numbers, for example if i call it to find "1". What's wrong?

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high)/2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid + 1
        else:
            low = mid + 1
    return None

list1 = []

for i in range (1, 101):
    list1.append(i)

print(list1)
print(binary_search(list1, 1))

I'd highly recommend learning how to use a GUI debugger, like Pycharm's, to figure out exactly how your program executes, since that'd make it trivial to understand the issue in not just this code, but almost any code. — Random Davis
– Random Davis, Commented Mar 19, 2021 at 15:31
Are you using python2? (low + high)/2 should return a float in python3 which will crash your program as floats cannot be used as indices. So if you're using python2, start with upgrading to python3, as python2 is no longer supported since 2020. — Ted Klein Bergman
– Ted Klein Bergman, Commented Mar 19, 2021 at 15:34
Also, it looks like your issue is just a simple typo. You set high = mid + 1 if the guess is too high, but you also set low = mid + 1 otherwise. I'm pretty sure you meant low = mid - 1. — Random Davis
– Random Davis, Commented Mar 19, 2021 at 15:34
Also, don't use list as a variable name. list is already a built-in name and overriding it will most likely cause you issues in the future. — Ted Klein Bergman
– Ted Klein Bergman, Commented Mar 19, 2021 at 15:35
i use python 3, in the book it was mentioned that (low + high)/2 would automatically round the result if it's not an integer. Thank you all for answers, will certainly look into learning how to used GUI :) — ela rednax
– ela rednax, Commented Mar 19, 2021 at 16:21

trincot · Accepted Answer · 2021-03-19 16:40:16Z

2

Two issues:

Use integer division (so it will work in Python 3): mid = (low + high)//2
When guess > item you want to exclude the guessed value from the next range, but with high = mid + 1 it still is in the range. Correct to high = mid - 1

answered Mar 19, 2021 at 16:40

trincot

357k38 gold badges282 silver badges338 bronze badges

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

2 Comments

ela rednax Over a year ago

it helped, however the problem was not in "high" equation, but in "low" one - it should be = mid -1, since we were trying to find an item that was not in a first half of the list, so with second iteration we start looking for it in another bigger half. But your answer gave me the right direction to look for, thanks

trincot Over a year ago

Note sure what you mean. See it run here with the two corrections I mentioned. Anyhow, happy to hear it worked out for you.

Collectives™ on Stack Overflow

Why does binary search algorithm not work?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related