Binary Search

Q: Quelle est la complexité temporelle de la recherche binaire ?

O(log n) . Chaque comparaison divise par deux l’intervalle susceptible de contenir la cible ; après k étapes, il reste donc au plus n / 2^k candidats. Une liste de 10^4 éléments nécessite au plus 14 comparaisons, et une liste de 10^9 éléments au plus 30. La version itérative utilise un espace supplémentaire de O(1) .

Q: Pourquoi la recherche binaire nécessite-t-elle un tableau trié ?

L’étape qui élimine la moitié de la liste repose sur l’ordre. Lorsque nums[mid] < target , le tri garantit que chaque élément situé à gauche de mid est également inférieur à target , donc aucun d’eux ne peut correspondre. Dans une liste non triée, cette comparaison ne nous apprend rien sur les autres éléments, et il faut tous les vérifier.

Q: La recherche binaire doit-elle être itérative ou récursive ?

Les deux sont correctes et s’exécutent toutes deux en temps O(log n) . La version récursive s’appelle elle-même sur une moitié et utilise un espace de pile de O(log n) ; la version itérative déplace lo et hi dans une boucle et utilise O(1) . Les intervieweurs s’attendent généralement à la boucle, qui évite toute limite de récursion.

Q: Comment éviter un dépassement de capacité lors du calcul de l’indice du milieu ?

Écrivez mid = lo + (hi - lo) / 2 au lieu de (lo + hi) / 2 . Les deux donnent le même indice, mais la seconde forme additionne d’abord deux indices, et avec un entier de 32 bits, cette somme déborde lorsque les indices dépassent environ 1.07 × 10^9 . Python et Ruby utilisent des entiers non bornés, donc la forme courte y est sûre.

FacileRecherche binaire

+10

Vous recevez une liste d’entiers nums triée par ordre croissant, sans aucune valeur répétée, ainsi qu’un entier target. Renvoyez l’indice de target dans nums, en commençant à compter à partir de 0, ou -1 si cette valeur ne figure pas dans la liste. Visez un temps d’exécution de O(log n), ce qui signifie que vous ne pouvez pas vous permettre d’examiner chaque élément.

Fonction

search(nums: integer-array, target: integer) → integer

numsinteger-array: la liste triée d’entiers distincts
targetinteger: la valeur à rechercher
Renvoieinteger: l’index de target dans nums, ou -1 s’il est absent

Contraintes

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums est trié par ordre strictement croissant, donc chaque valeur apparaît une seule fois.

Exemples

Entrée: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
Sortie: 4
Explication: nums[4] vaut 9. La recherche examine l’indice 3 (valeur 4, trop petite), puis l’indice 5 (valeur 15, trop grande), puis l’indice 4, où elle trouve 9.

Entrée: nums = [1, 3, 5, 8, 13, 21]target = 10
Sortie: -1
Explication: 10 se trouverait entre 8 et 13, et aucun des deux n’est 10, donc il ne figure pas dans la liste. La plage de recherche rétrécit jusqu’à ce que lo dépasse hi, et la fonction renvoie -1.

+15 tests cachés à la soumission

Pour aller plus loin

Si nums pouvait contenir des valeurs répétées, comment renverrais-tu le premier indice de target, toujours en O(log n) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Parcourir les éléments un par un permet de trouver target, mais ignore le fait qui rend le problème intéressant : la liste est triée. Une seule comparaison avec l’élément du milieu vous indique quelle moitié peut encore contenir target, vous pouvez donc éliminer la moitié des candidats à chaque étape. Une liste de 10^4 éléments nécessite alors au maximum 14 comparaisons au lieu de 10000.

Parcourez de gauche à droite

Intuition

Vérifie chaque indice dans l’ordre et renvoie le premier dont la valeur est égale à target. Si la boucle se termine sans trouver de correspondance, target ne figure pas dans la liste ; renvoie donc -1. Chaque élément est comparé une seule fois, ce qui garantit que la réponse est correcte pour n’importe quelle liste, triée ou non.

Cette généralité pose problème. Pour une liste de 10^4 éléments, il faut jusqu’à 10000 comparaisons, et le travail augmente proportionnellement à n. Le parcours ne tient jamais compte du fait que nums est triée ; il ne respecte donc pas la borne O(log n) demandée par l’exercice. Tu pourrais t’arrêter dès qu’une valeur dépasse target, mais dans le pire des cas, tu lis quand même toute la liste.

Algorithme

Pour chaque indice i de 0 à n-1, compare nums[i] à target.
S'ils sont égaux, retourne i.
Après la boucle, retourne -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Recherche binaire avec deux index

Intuition

Conserve deux index, lo et hi, avec une garantie : si target se trouve dans la liste, son index est compris entre lo et hi, bornes incluses. Au départ, cette plage couvre toute la liste, de 0 à n-1. Examine l’index du milieu, mid. Si nums[mid] est égal à target, tu as terminé. S’il est plus petit, alors, puisque la liste est triée, chaque élément jusqu’à mid est lui aussi plus petit : déplace donc lo à mid + 1. S’il est plus grand, déplace hi à mid - 1. La garantie reste valable après l’un ou l’autre déplacement.

Suivons le premier exemple, [-7, -2, 0, 4, 9, 15, 23] avec target = 9. La plage de 0 à 6 a pour milieu 3, où se trouve la valeur 4, trop petite : la plage devient donc 4 à 6. Son milieu, 5, contient 15, trop grand : la plage devient donc 4 à 4. L’index 4 contient 9 : renvoie 4.

Si target est absent, la plage continue de rétrécir jusqu’à ce que lo dépasse hi. La plage est alors vide, la garantie indique que target ne se trouve nulle part, et tu renvoies -1. Chaque étape divise la plage par deux : la boucle s’exécute donc au plus environ log2(n) + 1 fois, soit 14 étapes pour 10^4 éléments. Deux index constituent toute la mémoire supplémentaire nécessaire.

Algorithme

Définissez lo = 0 et hi = n-1.
Tant que lo ≤ hi, calculez mid = lo + (hi - lo) / 2.
Si nums[mid] est égal à target, renvoyez mid.
Si nums[mid] < target, définissez lo = mid + 1 ; sinon, définissez hi = mid - 1.
Lorsque la boucle se termine, renvoyez -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

Pièges et cas limites

La recherche binaire est courte, et presque tous les bugs sont des erreurs de décalage d'une unité aux limites de l'intervalle.

Boucler tant que lo < hi alors que hi commence au dernier indice. La boucle s'arrête alors qu'il reste encore un candidat à vérifier, donc nums = [5] avec target = 5 renvoie -1. Avec un intervalle inclusif, boucle tant que lo ≤ hi.
Passer à lo = mid ou hi = mid avec un intervalle inclusif. Lorsque lo et hi sont voisins, mid est égal à lo et l'intervalle ne rétrécit jamais : c'est une boucle infinie. Tu as déjà vérifié nums[mid], alors passe au-delà avec mid + 1 ou mid - 1.
Calculer (lo + hi) / 2 dans un entier de largeur fixe. La somme déborde dès que les indices dépassent environ 10^9. Les limites ici sont bien inférieures, mais lo + (hi - lo) / 2 est une habitude sûre.
Renvoyer lo lorsque target est absent. Après la boucle, lo est le point d'insertion, qui est un indice valide, et non -1.
Oublier le décalage en Lua et R. Leurs listes commencent à 1, donc l'indice renvoyé est la position moins 1.

Questions fréquentes4

Quelle est la complexité temporelle de la recherche binaire ?

O(log n). Chaque comparaison divise par deux l’intervalle susceptible de contenir la cible ; après k étapes, il reste donc au plus n / 2^k candidats. Une liste de 10^4 éléments nécessite au plus 14 comparaisons, et une liste de 10^9 éléments au plus 30. La version itérative utilise un espace supplémentaire de O(1).

Pourquoi la recherche binaire nécessite-t-elle un tableau trié ?

L’étape qui élimine la moitié de la liste repose sur l’ordre. Lorsque nums[mid] < target, le tri garantit que chaque élément situé à gauche de mid est également inférieur à target, donc aucun d’eux ne peut correspondre. Dans une liste non triée, cette comparaison ne nous apprend rien sur les autres éléments, et il faut tous les vérifier.

La recherche binaire doit-elle être itérative ou récursive ?

Les deux sont correctes et s’exécutent toutes deux en temps O(log n). La version récursive s’appelle elle-même sur une moitié et utilise un espace de pile de O(log n) ; la version itérative déplace lo et hi dans une boucle et utilise O(1). Les intervieweurs s’attendent généralement à la boucle, qui évite toute limite de récursion.

Comment éviter un dépassement de capacité lors du calcul de l’indice du milieu ?

Écrivez mid = lo + (hi - lo) / 2 au lieu de (lo + hi) / 2. Les deux donnent le même indice, mais la seconde forme additionne d’abord deux indices, et avec un entier de 32 bits, cette somme déborde lorsque les indices dépassent environ 1.07 × 10^9. Python et Ruby utilisent des entiers non bornés, donc la forme courte y est sûre.

Python

def search(nums, target):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

Attendu