Binary search in Python results in an infinite loop

Question

list = [27 , 39 , 56, 73, 3, 43, 15, 98, 21 , 84]

found = False
searchFailed = False
first = 0
last = len(list) - 1
searchValue = int(input("Which number are you looking for? "))

while not found and not searchFailed:
    mid = (first + last) // 2
    if list[mid] == searchValue:
        found = True
    else:
        if first >= last :
            searchFailed = True
        else:
            if list[mid] > searchValue:
                last = mid - 1
            else:
                last = mid + 1

if found:
     print("Your number was found at location", mid)
else:
    print("The number does not exist within the list")

The code runs properly when I execute it while searching for 27 (the first number), but any other number just results in an infinite loop. I believe the loop runs smoothly on the first iteration since if I change the value of first to 1, the code correctly finds the position of 39 but repeats the infinite loop error with all the other numbers after that (while 27 "does not exist within the loop" which makes sense). So I suppose the value of mid is not getting updated properly.

Answer 1

Several points to cover here. First, a binary search needs sorted data in order to work. As your list is not sorted, weirdness and hilarity may ensue :-)

Consider, for example, the unsorted [27 , 39 , 56, 73, 3, 43, 15, 98, 21] when you're looking for 39.

The first midpoint is at value 3 so a binary search will discard the left half entirely (including the 3) since it expects 39to be to the right of that3. Hence it will never find 39`, despite the fact it's in the list.

If your list is unsorted, you're basically stuck with a sequential search.

---

Second, you should be changing first or last depending on the comparison. You change last in both cases, which won't end well.

---

Third, it's not usually a good idea to use standard data type names or functions as variable names. Because Python treats classes and functions as first-class objects, you can get into a situation where your bindings break things:

>>> a_tuple = (1, 2) ; a_tuple
(1, 2)

>>> list(a_tuple)                  # Works.
[1, 2]

>>> list = list(a_tuple) ; list    # Works, unintended consequences.
[1, 2]

>>> another_list = list(a_tuple)   # No longer works.
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'list' object is not callable

---

Covering those issues, your code would look something like this (slightly reorganised in the process):

my_list = [3, 15, 21, 27, 39, 43, 56, 73, 84, 98]

found = False
first, last = 0, len(my_list) - 1
searchValue = int(input("Which number are you looking for? "))

while not found:
    if first > last:
        break
    mid = (first + last) // 2
    if my_list[mid] == searchValue:
        found = True
    else:
        if my_list[mid] > searchValue:
            last = mid - 1
        else:
            first = mid + 1

if found:
     print("Your number was found at location", mid)
else:
    print("The number does not exist within the list")

---

That works, according to the following transcript:

pax> for i in {1..6}; do echo; python prog.py; done

Which number are you looking for? 3
Your number was found at location 0

Which number are you looking for? 39
Your number was found at location 4

Which number are you looking for? 98
Your number was found at location 9

Which number are you looking for? 1
The number does not exist within the list

Which number are you looking for? 40
The number does not exist within the list

Which number are you looking for? 99
The number does not exist within the list

Answer 2

First of all, do not use any reserved word (here list) to name your variables. Secondly, you have a logical error in the following lines:

if list[mid] > searchValue:
    last = mid - 1
else:
    last = mid + 1

In the last line of the above snippet, it should be first = mid + 1

Answer 3

There are very good answers to this question, also you can consider this simpler version adapted to your case:

my_list = [3, 15, 21, 27, 39, 43, 56, 73, 84, 98]  # sorted!

left, right = 0, len(my_list)  # [left, right)
search_value = int(input("Which number are you looking for? "))

while left + 1 < right:
    mid = (left + right) // 2
    if my_list[mid] <= search_value:
        left = mid
    else:
        right = mid

if my_list[left] == search_value:  # found!
     print("Your number was found at location", left)
else:
    print("The number does not exist within the list")

Answer 4

The problem with your function is that in Binary Search the array or the list needs to be SORTED because it's one of the most important principal of binary search, i made same function working correctly for you

#low is the first index and high is the last index, val is the value to find, list_ is the list, you can leave low as it is
def binary_search(list_: list, val,high: int, low: int = 0):
    mid = (low+high)//2
    if list_[mid] == val:
        return  mid
    elif list_[mid] <= val:
        return binary_search(list_, val, high+1)
    elif list_[mid] >= val:
        return binary_search(list_, val, high, low-1)

and now here's the output

>>> binary_search(list_, 21, len(list_)-1)
>>> 2

what will happen here is that first it will calculate the middle index of the list, which i think of your list is 5, then it will check whether the middle value is equal to the value given to search, and then return the mid index, and if the mid index is smaller than the value, then we will tell it to add one to high index, and we did the comparison with index and value because as i told you, list needs to be sorted and this means if index is greater or equal to the mid index then the value is also surely greater than the middle value, so now what we will do is that we will call the same function again but this time with a higher high which will increase the mid point and if this time middle index is equal to value, then its gonna return the value and going to do this untill mid is equal to value, and in the last elif it says if middle value is greater than value, we will call same function again but lower the low i.e which is 0 and now -1, which will reduce the mid point and this whole process will continue untill mid is equal to value