Recherche binaire : diviser l'espace par deux

Sur des données triées, on élimine la moitié des candidats à chaque étape : O(log n) au lieu de O(n).

On compare la valeur du milieu à la cible, puis on ne garde que la moitié qui peut la contenir. Pour 10⁹ éléments, il suffit d'environ 30 comparaisons.

Version classique#

function binarySearch(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);     // évite le dépassement (lo + hi)
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Piège : (lo + hi) / 2 peut dépasser la capacité d'un entier 32 bits en C ou Java. Écrivez lo + (hi - lo) / 2. Les erreurs « off-by-one » (< contre <=, mid contre mid ± 1) sont l'autre grande source de bugs.

Première position possible (lower bound)#

Le patron le plus utile : « premier index dont la valeur est ≥ cible », qui sert pour les doublons, les insertions ou les bornes.

function lowerBound(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length;                             // hi exclu : le résultat peut valoir n
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Recherche binaire sur la réponse#

Quand on cherche « la plus petite valeur telle que… » et que la condition est monotone (faux…faux, vrai…vrai), on cherche binairement la réponse elle-même, pas dans un tableau. Exemples : capacité minimale pour livrer en D jours, vitesse minimale pour manger toutes les piles à temps.

Astuce : la question à se poser est « puis-je écrire une fonction possible(x) monotone ? ». Si oui, la recherche binaire sur x donne un O(log(plage) × coût de possible).