28. Applications Avancées de la Binary Search

La Binary Search ne sert pas seulement à trouver des correspondances exactes. C'est un outil puissant pour trouver des limites et optimiser des fonctions.

1. Trouver la Première/Dernière Occurrence

Si un tableau contient des doublons (par exemple, [2, 4, 4, 4, 5]), la recherche binaire standard pourrait renvoyer n'importe lequel des 4. En modifiant légèrement la logique de comparaison, nous pouvons spécifiquement trouver l'index du premier 4 ou du dernier 4.

2. Rechercher dans des Tableaux Triés et Pivotés (Rotated Sorted Arrays)

Imaginez [6, 7, 1, 2, 3, 4, 5]. Ce tableau est trié mais pivoté. La recherche binaire standard échoue. Cependant, comme au moins une moitié du tableau sera toujours triée, nous pouvons utiliser la recherche binaire en vérifiant à quelle moitié le pivot (élément central) appartient et en réduisant l'espace de recherche efficacement (O(log N)).

3. Optimisation de Fonction

Si la sortie d'une fonction est monotone (augmente ou diminue toujours), la recherche binaire peut être utilisée pour trouver la valeur d'entrée minimale nécessaire pour atteindre une sortie cible, réduisant drastiquement l'espace de recherche.