Recherche binaire

La recherche binaire est beaucoup plus rapide que la recherche lineaire, mais elle a une contrainte : la liste doit etre triee.

C'est comme chercher un mot dans un dictionnaire. Tu n'ouvres pas a la première page pour lire chaque mot. Tu ouvres au milieu, tu regardes si ton mot est avant ou apres, et tu recommences dans la bonne moitie. A chaque étape, tu elimines la moitie des possibilites.

Complexite : O(log n). Pour une liste d'un million d'éléments, il te faut au maximum 20 comparaisons au lieu d'un million.

Le principe :
- Tu maintiens deux bornes : gauche et droite
- Tu calcules le milieu : milieu = (gauche + droite) // 2
- Si lst[milieu] == cible, c'est gagne
- Si lst[milieu] < cible, la cible est a droite : gauche = milieu + 1
- Si lst[milieu] > cible, la cible est a gauche : droite = milieu - 1

Écris une fonction recherche_binaire(lst, cible) qui retourne l'index de cible dans une liste triee, ou -1 si absent.

Exemple :
recherche_binaire([1, 3, 5, 7, 9, 11], 7) renvoie 3
recherche_binaire([1, 3, 5, 7, 9, 11], 6) renvoie -1

Tests (3/4)

Élément trouve

assert recherche_binaire([1, 3, 5, 7, 9, 11], 7) == 3

Absent

assert recherche_binaire([1, 3, 5, 7, 9, 11], 6) == -1

Premier élément

assert recherche_binaire([2, 4, 6, 8], 2) == 0

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

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

← Recherche lineaire Recherche du minimum et maximum →

solution.py

Bravo!

Recherche binaire

Tests (3/4)

Indices (3 disponibles)

Solution officielle