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)

Is this supposed to be a normal binary search, or is there some extra functionality to it? This feels like a huge amount of code for what should be about half dozen lines and I'm having trouble determining the intent. Sorting the list on every iteration basically renders the algorithm useless from a performance standpoint. Also, keep in mind that there's a builtin for this. — ggorlen
– ggorlen, Commented Dec 31, 2019 at 20:44
Your function has a hole in the bottom which lets None escape! — quamrana
– quamrana, Commented Dec 31, 2019 at 20:50
@ggorlen: yes, this is just a normal binary search. It’s long because of the possibility that “key” might be repeated. The reason for the three nested if statements is me adjusting for various possibilities. But I am new to recursion so I do not know if it is unnecessary — Rahel Miz
– Rahel Miz, Commented Dec 31, 2019 at 21:06
The second half of your function is an if / elif chain which has no else. I also see that some of your elifs don't return something, therefore the function can fall to the bottom and return None by default. — quamrana
– quamrana, Commented Dec 31, 2019 at 21:47

ggorlen · Accepted Answer · 2019-12-31 22:32:06Z

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.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related