binary search recursive returns none

user_12276557 0
Viewed 450

I was trying to write binary search in python. What i write is :



arr = [6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 97]

def binarySearch(arr, low, high, key):
    if(low <= high):
        mid = (low + high) // 2
        if(arr[mid] == key):
            return key

        elif(arr[mid] > key):
            binarySearch(arr, low, mid - 1, key)

        else:
            binarySearch(arr, mid + 1, high, key)

    else:
        return -1

i = binarySearch(arr, 0, len(arr) - 1, 33)
print(i)

It returns None. Then i discovered that i did not put return statements at the beginning of recursive calls. But in my head, without return statements, it should return the key anyway, because first it controls if it matches with key. Why function keep executing after finding the key and returns None instead of key.

return recursion algorithm python
3 Answers

It does not return because you are not asking it to. However, I am guessing that if you DID put the return statements in, it would still return the wrong thing - the key, vs the index where key is situated (you know what key is, why would you want to do a computation to return it?)

user_29772560

Here is a non-recursive variation of binary search that you might consider.

def binary_search(arr, x):
    # Time O(log n)
    # Space O(1)
    left = 0; right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if x > arr[mid]:
            left = mid + 1
        elif x < arr[mid]:
            right = mid - 1
        else:
            return mid
    return False
user_105653750 
arr = [6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 97]


def binarySearch(arr, low, high, key):
    if(low <= high):
        mid = (low + high) // 2
        if(arr[mid] == key):
            return key

        elif(arr[mid] > key):
            return binarySearch(arr, low, mid - 1, key)

        else:
            return binarySearch(arr, mid + 1, high, key)

    else:
        return -1


i = binarySearch(arr, 0, len(arr) - 1, 33)
print(i)
user_138133650
Related