Rekurencyjna wersja wyszukiwania binarnego

Question

Mam za zadanie zaimplementować rekurencyjną wersję algorytmu przeszukiwania binarnego (dla listy indeksowanej od 0) w taki sposób, aby zwrócił indeks, na którym znajduje się element. Rekurencja sprawia mi jeszcze trochę kłopotów, więc bardzo proszę o wskazówkę co w poniższym kodzie jest do poprawy. Z góry dziękuje za wszelką pomoc. :)

import math
list = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def binarysearch(list, k):
    center = int((math.floor(len(list)/2)))
    if k in list:
        if list[center] == k:
            return center
        elif list[center] < k:
            return center + binarysearch(list[center:], k)
        elif list[center] > k:
            return center + binarysearch(list[:center], k)
    else:
        return None

 

Answer 1

Instrukcja

if k in list:

całkowicie zaburza sens przeszukiwania binarnego, wywal ją.
Jeżeli lista jest pusta, lub ma jeden element, który jest różny od poszukiwanego to zwróć None.
Resztę logiki zostawiasz, z małym wyjątkiem. Nie podoba mi się przeszukiwanie lewej części listy. Jeżeli element się tam znajduje to i tak otrzymasz indeks z prawej (lub nawet daleko poza listą). Niepotrzebnie dodajesz wartość center.