La recherche binaire divise l'espace de recherche en deux à chaque étape. Sur un tableau trié de n éléments, elle trouve une cible en O(log n).
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Simple - mais la vraie puissance de la recherche binaire va bien au-delà des tableaux triés.
La recherche binaire fonctionne dès qu'il existe une condition monotone sur un intervalle. Le « tableau » n'a même pas besoin d'exister - il suffit d'un intervalle [lo, hi] et d'une fonction qui passe de False à True à une certaine frontière.
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- answer
Au lieu de chercher dans un tableau, on cherche dans l'espace des réponses. La question devient : « Puis-je atteindre le résultat X ? » Si oui, on essaie plus petit ; sinon, plus grand.
Koko a n tas de bananes et h heures. Trouvez la vitesse minimale pour tout manger à temps.
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid # speed works, try slower
else:
lo = mid + 1 # too slow, go faster
return lo
L'espace des réponses est [1, max(piles)] et la condition est monotone - une vitesse plus élevée signifie toujours moins d'heures.
Sign in to join the discussion
Un tableau trié pivoté à un point : [4, 5, 6, 7, 0, 1, 2]. Une moitié est toujours triée. On compare mid avec lo pour déterminer laquelle, puis on vérifie si la cible tombe dans la moitié triée.
[4, 5, 6, 7, 0, 1, 2]
L M R
Left half [4..7] is sorted.
Target 1 not in [4..7] → search right.
Dans un tableau trié avec rotation [3,4,5,1,2], quelle moitié est triée quand mid=2 (valeur 5) ?
Pour trouver la première occurrence, quand on atteint la cible, on ne s'arrête pas - on pose hi = mid et on continue à chercher à gauche. Pour la dernière, on pose lo = mid + 1 et on cherche à droite.
Cette paire de recherches donne aussi le nombre d'occurrences : dernière - première + 1.
Un élément plus grand que ses deux voisins. Même dans un tableau non trié, la recherche binaire fonctionne : si nums[mid] < nums[mid + 1], le pic est à droite ; sinon, à gauche. O(log n).
Si les lignes sont triées et que le premier élément de chaque ligne est supérieur au dernier de la ligne précédente, on traite la matrice comme un seul tableau trié de m × n éléments. L'index k correspond à la ligne k // n, colonne k % n.
Trouver le plus grand entier x tel que x * x ≤ n. Espace de recherche : [0, n]. Binary search on answer classique.
def sqrt(n):
lo, hi = 0, n
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= n:
lo = mid + 1
else:
hi = mid - 1
return hi
Des problèmes comme « split array largest sum » ou « capacity to ship packages within D days » demandent de minimiser le pire cas. La réponse est monotone : si la capacité C fonctionne, C+1 aussi. On fait une recherche binaire sur C.
Pour « Capacity to Ship Packages in D Days », quel est l'espace de recherche ?
lo, hi = min_possible, max_possible
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid # mid works, try smaller
else:
lo = mid + 1 # mid fails, need larger
return lo
Ajustez hi = mid vs lo = mid selon que vous cherchez le premier True ou le dernier True.
Quelle est la complexité temporelle d'une binary search sur un espace de taille S avec une vérification de faisabilité en O(n) ?