Why is this Binary search algorithm returning None twice?

user_18127079 0
Viewed 101

Im starting to learn about Algorithms (using the grokkings algorithms book) and this is the binary search code that was in the book

def binary_search(list, item):

  low = 0
  high = len(list) - 1

  while low <= high: 
    mid = round((low + high) )
    guess = list[mid]
    
    if guess == mid:
      return mid

    if guess > mid: 
      high = mid - 1 

    else: 
      low = mid + 1

  return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

The first one is supposed to return 1 but it returns None twice, anyone know why?

binary-search algorithm python
2 Answers

Try comparing guess with item:

def binary_search(lst, item):
    low = 0
    high = len(lst) - 1
    while low <= high: 
        mid = (low + high) // 2
        guess = lst[mid]
        if guess < item:
            low = mid + 1
        elif guess > item: 
            high = mid - 1
        else:
            return mid
    return None


my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

Output:

1
None
user_63282560

In the code is suppose to be mid = (low + high) // 2, where // is whole division.

user_124231200
Related