La recherche binaire peut être utilisée non seulement pour trouver des éléments dans un tableau, mais aussi pour trouver les racines des équations et les valeurs des fonctions monotones (croissantes ou décroissantes).
Donnons-nous une fonction monotone
f et une valeur
C de cette fonction. Trouvez la valeur de l'argument
x de cette fonction, tel que
\(f(x)=C\).
Exemple de fonction monotone croissante :
Nous choisissons de telles limites où la valeur de la fonction est exactement supérieure et exactement inférieure à la valeur donnée. Choisissons la valeur au milieu de ce segment. S'il est inférieur à celui donné, nous déplaçons la bordure gauche au milieu du segment. Sinon, nous décalerons la bordure droite. Ensuite, nous répétons le processus de réduction des limites. Mais il y a un problème, c'est quand arrêter de chercher. En savoir plus
ici.
Par exemple, considérons le problème de trouver la racine carrée du nombre x. La racine carrée de x (notée par \(\sqrt x\)) est un nombre y tel que < span class="math-tex">\(y^2 = x\).
Formulons le problème comme suit : pour un nombre réel donné
x (
\(x >= 1\)) trouvez le racine carrée avec une précision d'au moins 5 caractères après le point.
Sélection de la bordure du segment pour la recherche
Puisque nous ne pouvons pas vérifier l'infinité des nombres, nous devons définir les limites de la recherche de la racine. Trouvons d'abord la bordure gauche, sélectionnons un point négatif arbitraire (par exemple : -1). Nous le doublerons jusqu'à ce que la valeur qu'il contient soit supérieure à la valeur donnée. Afin de trouver la bonne frontière, on choisit un point positif arbitraire (par exemple : 1). Nous le doublerons jusqu'à ce que la valeur de la fonction à ce stade soit inférieure à celle spécifiée.
Ou, si nous connaissons exactement les limites de la recherche, nous pouvons prendre 1 comme limite gauche, et le nombre lui-même
x.
Après cela, nous divisons le segment actuel en deux, équarrissons le milieu, et s'il est supérieur à x, nous remplaçons la face supérieure, sinon en bas.
Mise en œuvre finale :