[Solved] Recursive Binary search algorithm – Python [closed]

by


Your existing function has at least two major problems: It doesn’t return the value from the recursive calls, meaning that it usually ends up returning None if it finishes; it uses the wrong bounds to slice the list, meaning half the time it ends up with infinite recursion.

If you fix those, then all you have to do is return the index instead of True, and something else (e.g., -1, or raise an exception) instead of False. That means the recursive calls will get the index into the slice instead of the whole list, but they know the offset and can adjust it.

So, first:

if len(L) == 1:
    if L[0] == val:
        # return True
        return 0
    else:
        # return False
        raise ValueError('not found')
else:
    hi = len(L)
    lo = 0
    mid = (hi + lo)//2
    if val == L[mid]:
        # return True
        return mid
    elif val > L[mid]:
        # return bin_search(val,L[mid + 1:])
        return mid + 1 + bin_search(val,L[mid + 1:])
    elif val < L[mid]:
        # no change here, because the offset is 0
        return bin_search(val,L[:mid])

And that’s it. It should be obvious that this is doing the exact same sequence of recursive calls, and the only extra work is adding mid + 1 in just under half the cases, so it still has the same complexity.

solved Recursive Binary search algorithm – Python [closed]