While loop will not stop in recursive binary search

Question

I am trying to program a recursive binary search algorithm in python. However, I keep running into an infinite while-loop. I am afraid that it must be something simple that I am overlooking, but I cannot find the answer anywhere, most questions about while-loops not terminating do use other conditions and not boolean values.

The algorithm does seem to work, it prints the index of the element that I am searching for, or "Value not found" when the element is not in the list. But the while loop does never terminates, Even though i set found = False after the value has been found/not found. Why is this?

def binarysearch(A, v, x, y):
found = True
while found:
    if x < y:
        h = (x+y) //2
        if A[h] < v:
            binarysearch(A, v, h+1, y)
        else:
            binarysearch(A, v, x, h)
    elif A[x] == v:
        found = False
        print("Element you are looking for is at index {}".format(x))
    else:
        found = False
        print("Value is not in array")

#Code to test the binarysearch algorithm
blist = []
for value in range(0,124):
    if value % 2 ==0:
        blist.append(value)

print(blist)
binarysearch(blist, 68, 0, len(blist)-1)

Answer 1

The found variable you are modifying with found = False is local to the scope of that particular recursive call to binarysearch. It is not the instance of found you are trying to modify, i.e. the one in the top level of the recursion tree. So although the while-loop in the current scope will terminate, the loops in the scopes above it will not.

Since you already have a mostly complete loop implementation, instead of using recursion on top of it (which is causing the scope-related error) you can just narrow the search range by overwriting x and y.

def binarysearch(A, v, x, y):
    found = True
    while found:
        if x < y:
            h = (x+y) //2
            if A[h] < v:
                x = h+1  // replaced
            else:
                y = h    // replaced
        elif A[x] == v:
            found = False
            print("Element you are looking for is at index {}".format(x))
        else:
            found = False
            print("Value is not in array")