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

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