Рекурсивный бинарный поиск, который возвращает индекс

Question

Я нахожусь во введении в класс CS и получил задание для выполнения рекурсивного двоичного поиска, который возвращает индекс искомого элемента, если он присутствует в списке, в противном случае он должен возвращать отрицательный.

Код, который классифицирует функцию, выглядит следующим образом: (python code)

numList = [1,2,3,4,5,...6,7,8,9]
key = <insert number to search for here>
position = binarySearch(numList, key)
print("Your number is at " + str(position))

Мне не разрешено изменять аргументы функции.

учитывая

def binarySearch(numList, key):
   <code here>

Любые советы о том, как это сделать sh? Мне всегда кажется, что я не могу восстановить индекс исходного числа. Двоичный поиск должен быть рекурсивным.

Answer 1

скопированный бинарный поиск из geeksforgeeks

реализовать код в соответствии с формулировкой проблемы

numList = [1,2,3,4,5,6,7,8,9]
key = 6

def binarySearch(numList, key):
    def binary_search(alist, start, end, key):
        """Search key in alist[start... end - 1]."""
        if not start < end:
            return -1

        mid = (start + end)//2
        if alist[mid] < key:
            return binary_search(alist, mid + 1, end, key)
        elif alist[mid] > key:
            return binary_search(alist, start, mid, key)
        else:
            return mid
    return binary_search(numList, 0, len(numList), key)

print(binarySearch(numList, key)) # otput 5, index start from 0