I am attempting to create a binary search program for a school project, but certain numbers cause infinite recursion

Question

This is my code:

list = []
line = 50

def genList(list):
    i = 0
    while i < 1000:
        list.append(i)
        i += 1
    return list

def displayList(list, line):
    i = 0
    while i < 1000:
        if i != 0 and i % line == 0:
            print('\n')
        print('{0:03}'.format(list[i]), end = ' ')
        i += 1
    print('\n')

def binarySearch(min, max, list, goal):
    mid = min + (max - 1) // 2
    if list[mid] == goal:
        return mid
    elif list[mid] > goal:
        return binarySearch(min, mid - 1, list, goal)
    else:
        return binarySearch(mid + 1, max, list, goal)

genList(list)
displayList(list, line)
goal = int(input('What number do you want to find, from 0 to 999?\n'))

result = binarySearch(0, len(list) - 1, list, goal)
print(result)

...and like I said, certain numbers work but others don't, for example 999 will return 999 but 998 will return:

RecursionError: maximum recursion depth exceeded in comparison

Anyone know what's wrong with it? I'm at a bit of a loss...

Answer 1

This line is definitely wrong:

mid = min + (max - 1) // 2

Perhaps you meant ( as @Nikolaos Chatzis pointed out)

mid = min + (max - min) // 2

but following works as well and needs one less operation:

mid = (min + max) // 2

Additionally you should abort recursion if minval > maxval (if the value you search for is not in the list)

I didn't look if you can do better. but this should work

def binarySearch(minval, maxval, list_, goal):
    mid = (minval + maxval) // 2
    # print(minval, maxval, mid, goal)  # uncomment for debugging
    if minval > maxval:  # couldn't find search value
        return None
    if list_[mid] == goal:
        return mid
    elif list_[mid] > goal:
        return binarySearch(minval, mid - 1, list_, goal)
    else:
        return binarySearch(mid + 1, maxval, list_, goal)

Also don't hesitate to add print statements (or logs) for debugging.

It makes it very often obvious what is going wrong.

What you could also do is run some simple test code to show that it works for all cases:

for v in range(1000):
    assert binarySearch(0, len(list_) -1, list_, v) == v

Also as general recommendation to not stumble into funny or strange bugs.

min, max and list are all python keywords. You can avoid funny surprises by not using variables with these names. It makes your code also look better with many basic syntax highlighters.

Using them as variable names is not forbidden, but I think it's not a good idea.