Pièges de la recherche binaire : dépassement de capacité du point médian et bornes décalées d'une unité

Ce que c'est

La recherche binaire trouve une position dans des données triées en divisant en deux, à répétition, la plage candidate. Trois erreurs reviennent. D'abord, le dépassement de capacité du point médian : l'article cité de Google Research décrit comment (low + high) / 2 échoue dans le binarySearch du JDK dès que la somme dépasse le maximum d'un int, et propose low + ((high - low) / 2) ou (low + high) >>> 1 comme corrections. Ensuite, la convention de bornes : que high soit inclusif ou exclusif détermine la condition de boucle et les mises à jour ; mélanger les conventions produit des boucles infinies ou un élément sauté. Enfin, les doublons : la documentation de bisect en Python décrit bisect_left (point d'insertion avant les entrées égales) et bisect_right (après), soit la différence entre « première correspondance » et « position après la dernière correspondance ». Le sort.Search de Go évite l'essentiel de cela en demandant le plus petit indice de [0, n) où un prédicat monotone devient vrai.

Pourquoi c'est important

Cette routine apparaît dans les curseurs de pagination, les recherches sur des séries temporelles, les vérifications de plages de version, les recherches de type git bisect sur des builds, et de nombreuses tâches « trouver le premier qui échoue ». Une borne erronée est silencieuse : les résultats sont décalés d'une unité seulement pour certaines entrées, typiquement le premier ou le dernier élément.

Comment l'appliquer

• Préférer la fonction de bibliothèque (bisect, sort.Search, Arrays.binarySearch) ; n'en écrire une soi-même que lorsque le prédicat n'est pas une recherche dans un tableau.
• Utiliser la forme à prédicat : trouver le premier indice où pred(i) est vrai, en exigeant que pred soit faux puis vrai sur toute la plage. La borne inférieure, la borne supérieure et « première version en échec » en sont toutes des instances.
• Utiliser un intervalle semi-ouvert : lo, hi = 0, n ; tant que lo < hi : mid = lo + (hi - lo) // 2 ; si pred(mid) : hi = mid sinon lo = mid + 1 ; renvoyer lo. Le + 1 de la branche « sinon » garantit la progression.
• Tester les bords : entrée vide, un seul élément, cible en dessous du premier et au-dessus du dernier, tous les éléments égaux, cible à l'indice 0 et n-1.
• Vérifier que les données sont triées selon la même comparaison que celle utilisée pour la recherche (bisect avec key= doit correspondre à la clé de tri).

Pièges

Les entiers Python ne débordent pas, mais les erreurs de bornes subsistent. Une recherche sur des flottants se casse en présence de NaN, car les comparaisons cessent de constituer un ordre. Des données triées avec un ordre de collation propre à une locale et recherchées octet par octet ne sont pas triées pour cette recherche. bisect_left renvoie un point d'insertion pour les valeurs absentes, pas -1 : vérifier i < len(a) and a[i] == x. La recherche binaire sur une liste chaînée est linéaire, car l'indexation l'est aussi.