Рекурсивная реализация бинарного поиска

Условие

Необходимо преобразовать текущую итеративную реализацию бинарного поиска в рекурсивную. Функция получает отсортированный массив и искомое значение, должна вернуть позицию найденного элемента или -1, если элемент отсутствует.

sorted_arr = [1, 5, 7, 10, 20, 100]

def binary_search_recursive(sorted_arr, key):
    ...

Ответ

Передавайте рекурсивному помощнику границы поиска, не копируя срезы массива. На каждом шаге сравнивайте средний элемент с key и оставляйте одну половину; при пустом диапазоне возвращайте -1.

Реализация для массива по возрастанию:

def binary_search_recursive(sorted_arr, key):
    def search(left, right):
        if left > right:
            return -1
        middle = (left + right) // 2
        if sorted_arr[middle] == key:
            return middle
        if sorted_arr[middle] < key:
            return search(middle + 1, right)
        return search(left, middle - 1)
    return search(0, len(sorted_arr) - 1)

Для key=20 в примере результат 4. При дубликатах возвращается один подходящий индекс, не обязательно первый. Время и глубина рекурсии O(log n); пустой массив корректно даёт -1.