Why is my recursive search function not working?-CodePudding

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

CodePudding user response：

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

CodePudding user response：

You need to return the result of the recursive call to binary_search_recursive():

binary_search_recursive(array, left   1, right, key)

should be

return binary_search_recursive(array, left   1, right, key)

Note that this is not a binary search algorithm; you're enumerating one element at a time (using recursion), so this is really a sequential search.

CodePudding user response：

You need to tab in the second return. Try:

                            key: int) -> int:
    if left <= right:
        if array[left] == key:
            return left
        else:
            binary_search_recursive(array, left   1, right, key)
            return -1 #Moved to the right.