Recursive binary search algorithm doesn't stop executing after condition is met, returns a nonetype object

Question

I have made a binary search algorithm, biSearch(A, high, low, key). It takes in a sorted array and a key, and spits out the position of key in the array. High and low are the min and max of the search range.

It almost works, save for one problem:

On the second "iteration" (not sure what the recursive equivalent of that is), a condition is met and the algorithm should stop running and return "index". I commented where this happens. Instead, what ends up happening is that the code continues on to the next condition, even though the preceding condition is true. The correct result, 5, is then overridden and the new result is a nonetype object. within my code, I have commented in caps the problems at the location in which they occur. Help is much appreciated, and I thank you in advance!

"""
Created on Sat Dec 28 18:40:06 2019


"""
def biSearch(A, key, low = False, high = False):
    if low == False: 
        low = 0

    if high == False:
        high = len(A)-1

    if high == low: 
        return A[low]


    mid = low + int((high -low)/ 2)

                                                    # if key == A[mid] : two  cases
    if key == A[mid] and high - low == 0:                           #case 1: key is in the last pos. SHOULD STOP RUNNING HERE  

        index = mid 
        return index 
    elif key == A[mid] and (high - low) > 0:                              
        if A[mid] == A[mid + 1] and A[mid]==A[mid -1]:              #case 2: key isnt last and might be repeated
            i = mid -1                                  
            while A[i] == A[i+1]:
                  i +=1
                  index = list(range(mid- 1, i+1))

        elif A[mid] == A[mid + 1]:
            i = mid
            while A[i]== A[i+1]:
                i += 1
                index = list(range(mid, i+1))


        elif A[mid] == A[mid -1]:
            i = mid -1
            while A[i] == A[i +1]:
                i += 1
                index = list(range(mid, i +1))


    elif key > A[mid] and high - low > 0:           # BUT CODE EXECTUES THIS LINE EVEN THOUGH PRECEDING IS ALREADY MET
        index = biSearch(A, key, mid+1, high)



    elif key <  A[mid] and high - low > 0:
        index = biSearch(A, key, low, mid -1) 

        return index

    elif A[mid] != key:                         # if key DNE in A
        return -1




#biSearch([1,3,5, 4, 7, 7,7,9], 1, 8, 7)
#x = biSearch([1,3,5, 4, 7,9], 1, 6, 9)


x = biSearch([1,3,5, 4, 7,9],9)
print(x)
# x = search([1,3,5, 4, 7,9], 9)

Answer 1

This function is not a binary search. Binary search's time complexity should be O(log(n)) and works on pre-sorted lists, but the complexity of this algorithm is at least O(n log(n)) because it sorts its input parameter list for every recursive call. Even without the sorting, there are linear statements like list(range(mid, i +1)) on each call, making the complexity quadratic. You'd be better off with a linear search using list#index.

The function mutates its input parameter, which no search function should do (we want to search, not search and sort).

Efficiencies and mutation aside, the logic is difficult to parse and is overkill in any circumstance. Not all nested conditionals lead to a return, so it's possible to return None by default.

You can use the builtin bisect module:

>>> from bisect import *
>>> bisect_left([1,2,2,2,2,3,4,4,4,4,5], 2)
1
>>> bisect_left([1,2,2,2,2,3,4,4,4,4,5], 4)
6
>>> bisect_right([1,2,2,2,2,3,4,4,4,4,5], 4)
10
>>> bisect_right([1,2,2,2,2,3,4,4,4,4,5], 2)
5
>>> bisect_right([1,2,2,2,2,3,4,4,4,4,5], 15)
11
>>> bisect_right([1,2,5,6], 3)
2

If you have to write this by hand as an exercise, start by looking at bisect_left's source code:

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if a[mid] < x: lo = mid+1
        else: hi = mid

This is easy to implement recursively (if desired) and then test against the builtin:

def bisect_left(a, target, lo=0, hi=None):
    if hi is None: hi = len(a)

    mid = (hi + lo) // 2

    if lo >= hi: 
        return mid
    elif a[mid] < target:
        return bisect_left(a, target, mid + 1, hi)

    return bisect_left(a, target, lo, mid)

if __name__ == "__main__":
    from bisect import bisect_left as builtin_bisect_left
    from random import choice, randint
    from sys import exit

    for _ in range(10000):
        a = sorted(randint(0, 100) for _ in range(100))

        if any(bisect_left(a, x) != builtin_bisect_left(a, x) for x in range(-1, 101)):
            print("fail")
            exit(1)

Logically, for any call frame, there's only 3 possibilities:

• The lo and hi pointers have crossed, in which case we've either found the element or figured out where it should be if it were in the list; either way, return the midpoint.
• The element at the midpoint is less than the target, which guarantees that the target is in the tail half of the search space, if it exists.
• The element at the midpoint matches or is less than the target, which guarantees that the target is in the front half of the search space.

Python doesn't overflow integers, so you can use the simplified midpoint test.