Comment faire une recherche binaire

Précédent ◈ Suivant

Il est possible de tirer un meilleur parti de la liste ordonnée si nous sommes intelligents avec nos comparaisons. Dans la recherche séquentielle, lorsque l'on compare contre le premier élément, il y a au plus \ (n-1 \) d'autres éléments à regarder à travers si le premier élément est pas ce que nous recherchons. Au lieu de chercher la liste dans l'ordre, une recherche binaire commencera par l'examen du point milieu. Si cet élément est celui que nous recherchons, nous fait. Si ce n'est pas l'élément, nous pouvons utiliser la nature ordonnée de la liste pour éliminer la moitié des éléments restants. Si l'élément que nous recherchons est supérieur au point milieu, nous savons que toute la moitié inférieure de la liste ainsi que l'élément du milieu peut être éliminé de toute considération ultérieure. L'élément, si elle est dans la liste, doit être dans la moitié supérieure.

On peut alors répéter le processus avec la moitié supérieure. Commencez au point milieu et le comparer à ce que nous recherchons. Encore une fois, nous trouvons soit ou divisé la liste en deux, éliminant ainsi une autre grande partie de notre possible espace de recherche. La figure 3 montre comment cet algorithme peut trouver rapidement la valeur 54. La fonction complète est affichée dans CodeLens 3.

Figure 3: Recherche binaire d'une liste ordonnée de Entiers

Binary Recherche d'une liste ordonnée (search3)

Avant de passer à l'analyse, il convient de noter que cet algorithme est un excellent exemple d'une stratégie de diviser pour mieux régner. Diviser pour régner signifie que nous diviser le problème en petits morceaux, résoudre les petits morceaux d'une certaine façon, puis réassembler le problème pour obtenir le résultat. Lorsque nous effectuons une recherche binaire d'une liste, nous vérifions d'abord l'élément du milieu. Si l'élément que nous recherchons est inférieur au point milieu, nous pouvons simplement effectuer une recherche binaire de la moitié gauche de la liste initiale. De même, si l'élément est plus, nous pouvons effectuer une recherche binaire de la moitié droite. De toute façon, ceci est un appel récursif à la fonction de recherche binaire passer une petite liste. CodeLens 4 montre cette version récursive.

Une recherche binaire - Version récursive (search4)

5.4.1. Analyse des Binary Search¶

Pour analyser l'algorithme de recherche binaire, il faut rappeler que chaque comparaison élimine environ la moitié des éléments restants de considération. Quel est le nombre maximum de comparaisons cet algorithme, il faudra vérifier la liste? Si nous commençons avec des articles n, environ \ (\ frac \) éléments seront laissés après la première comparaison. Après la deuxième comparaison, il y aura environ \ (\ frac \). Alors \ (\ frac \). \ (\ Frac \). etc. Combien de fois peut-on diviser la liste? Le tableau 3 nous aide à voir la réponse.

Tableau 3: Analyse tabulaires pour une recherche binaire ¶

Nombre approximatif d'éléments gauche

Lorsque nous avons divisé les temps de liste assez, nous nous retrouvons avec une liste qui a un seul élément. Soit c'est l'élément que nous recherchons ou non. De toute façon, nous fait. Le nombre de comparaisons nécessaires pour arriver à ce point i est où \ (\ frac = 1 \). La résolution de i nous donne \ (i = \ log n \). Le nombre maximum de comparaisons est logarithmique par rapport au nombre d'éléments dans la liste. Par conséquent, la recherche binaire est \ (O (\ log n) \).

Une question d'analyse supplémentaire doit être pris en compte. Dans la solution récursive ci-dessus, l'appel récursif,

utilise l'opérateur de la tranche pour créer la moitié gauche de la liste qui est ensuite transmis à l'invocation suivante (de même pour la moitié droite aussi). L'analyse que nous avons supposé ci-dessus que l'opérateur de la tranche prend du temps constant. Cependant, nous savons que l'opérateur de la tranche en Python est en fait O (k). Cela signifie que la recherche binaire en utilisant tranche ne fonctionnera pas dans le strict temps logarithmique. Heureusement, on peut y remédier en adoptant la liste ainsi que le début et la fin des indices. Les indices peuvent être calculés comme nous l'avons fait dans le Listing 3. Nous quittons cette mise en œuvre comme un exercice.

(A) 11, 5, 6, 8
On dirait que vous pourriez être coupable d'une erreur hors par un. Rappelez-vous la première position est l'index 0.
(B) 12, 6, 11, 8
recherche binaire commence au milieu et réduit de moitié la liste à chaque fois.
(C) 3, 5, 6, 8
recherche binaire ne démarre pas au début et à la recherche séquentielle, ses départs au milieu et réduit de moitié la liste après chaque comparaison.
(D) 18, 12, 6, 8
Il semble que vous commencez à partir de la fin et réduire de moitié la liste à chaque fois.

(A) 11, 14, 17
On dirait que vous pourriez être coupable d'une erreur hors par un. Rappelez-vous la première position est l'index 0.
(B) 18, 17, 15
Rappelez-vous la recherche binaire commence au milieu et réduit de moitié la liste.
(C) 14, 17, 15
On dirait que vous pourriez être hors d'un, veillez à ce que vous calculez le midpont en utilisant l'arithmétique entière.
(D) 12, 17, 15
recherche binaire commence au milieu et réduit de moitié la liste à chaque fois. Il se fait lorsque la liste est vide.

Articles Liés

Précédent ◈ Suivant