Recherche binaire récursive

Tu as deja implémente la recherche binaire avec une boucle while. Maintenant, refais-la de facon récursive.

Le principe est le meme : a chaque appel, tu divises la zone de recherche par 2. Mais au lieu d'une boucle, tu rappelles la fonction avec des bornes ajustees.

Les paramètres gauche et droite delimitent la zone de recherche. Au premier appel, gauche = 0 et droite = len(lst) - 1.

Le cas de base : si gauche > droite, la zone est vide, l'élément n'est pas la.
Le cas recursif : tu calcules le milieu, tu compares, et tu rappelles la fonction sur la bonne moitie.

Écris une fonction recherche_binaire_recursive(lst, cible, gauche=0, droite=None) qui retourne l'index de cible dans une liste triee, ou -1 si absent.

Exemple :
recherche_binaire_recursive([1, 3, 5, 7, 9], 5) renvoie 2
recherche_binaire_recursive([1, 3, 5, 7, 9], 4) renvoie -1

Tests (3/4)

Élément au milieu

assert recherche_binaire_recursive([1, 3, 5, 7, 9], 5) == 2

Absent

assert recherche_binaire_recursive([1, 3, 5, 7, 9], 4) == -1

Dernier élément

assert recherche_binaire_recursive([2, 4, 6, 8, 10], 10) == 4

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def recherche_binaire_recursive(lst, cible, gauche=0, droite=None):
    if droite is None:
        droite = len(lst) - 1
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if lst[milieu] == cible:
        return milieu
    elif lst[milieu] < cible:
        return recherche_binaire_recursive(lst, cible, milieu + 1, droite)
    else:
        return recherche_binaire_recursive(lst, cible, gauche, milieu - 1)

← Tours de Hanoi Insertion dans un BST →

solution.py

Bravo!

Recherche binaire récursive

Tests (3/4)

Indices (3 disponibles)

Solution officielle