Why is my recursive search function not working?

March 18, 2022

I need to write a simple recursive function that searches through an array from the index: left to index: right. We don’t have to worry about invalid left and right inputs, which are always correct. If there is a value in the array equal to the key, it returns the index of that value. If the key isn’t in the array, it returns -1.
I really don’t know why my function doesn’t work. I think it should. It only works if the key is the first index of the array.

def binary_search_recursive(array: List[int], left: int, right: int,
                            key: int) -> int:
    if left <= right:
        if array[left] == key:
            return left
        else:
            binary_search_recursive(array, left + 1, right, key)
    return -1

Test:

binary_search_recursive([0,1,5,6,23,45], 0, 5, 5)

Should return:

Returns:

-1

>Solution :

To fix your code, you need to return the else statement :

def binary_search_recursive(array: list[int], left: int, right: int,
                            key: int) -> int:
    if left <= right:
        if array[left] == key:
            return left
        else:
            return binary_search_recursive(array, left + 1, right, key)
    return -1

But still, it is not a binary search.

EDIT: A real binary search would be some thing like below:

def binary_search_recursive(array: list[int], left: int, right: int,
                            key: int) -> int:
    if right >= left:

        center = (right + left) // 2

        if array[center] == key:
            return center

        elif array[center] > key:
            return binary_search_recursive(array, left, center - 1, key)
        else:
            return binary_search_recursive(array, center + 1, right, key)
    return -1