Complexité du temps de recherche binaire
La recherche binaire est un paradigme de division et de conquête. Il recherche un élément dans un tableau trié. Dans cet article, seul le tri ascendant est considéré. L'élément à rechercher est appelé la valeur cible. La valeur cible peut être trouvée ou non dans le tableau.
La recherche commence par comparer la valeur cible avec l'élément moyen du tableau trié. Si le nombre d'éléments dans le tableau est égal, alors l'élément à la moitié du nombre est considéré comme l'élément moyen. Si la valeur cible est la même que l'élément moyen, l'indice de valeur cible a été trouvé. S'ils ne sont pas les mêmes, alors la valeur cible est plus grande ou plus petite que l'élément moyen. S'il est plus grand, la moitié inférieure du tableau sera abandonnée pour que la recherche continue dans la moitié supérieure. S'il est plus petit, la moitié supérieure du tableau sera abandonnée, pour que la recherche continue dans la moitié inférieure.
La recherche continue en divisant la moitié choisie en deux. Une comparaison entre la valeur cible et l'élément moyen de cette nouvelle moitié est faite. S'ils ne sont pas les mêmes, alors cette moitié est à nouveau divisée en deux et pour les mêmes raisons, la moitié précédente a été divisée. Si la valeur cible n'est pas la même que le nouvel élément moyen, alors la division continue.
Lorsque la valeur cible et une valeur médiane (élément) sont les mêmes, c'est-à-dire conquérir. Là-bas, la recherche s'arrête. Si la valeur cible n'est pas dans le tableau, la recherche s'arrêtera à un élément moyen final, qui n'est pas égal à la valeur cible.
Cet article vise à donner une appréciation appelée complexité temporelle pour la vitesse de la recherche binaire.
Contenu de l'article
- Introduction - Voir ci-dessus
- Illustration de recherche binaire
- Complexité du temps et recherche binaire
- Codage en c
- Conclusion
Illustration de recherche binaire
Considérez la liste triée:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16Où l'entier, 3 ans, doit être fouillé. Bien sûr, la recherche dès le début prendra trois opérations. Cependant, l'utilisation de la recherche binaire prendra quatre opérations principales comme suit:
La valeur cible est 3. La division de la liste en deux fait 8 l'élément moyen.
Est 8 comme 3?
Non. Puisque 3 est inférieur à 8, la recherche se concentrera sur la moitié inférieure. C'est une opération principale faite.
La division en deux fait à nouveau 4 fait 4 le nouvel élément moyen.
Est 4 comme 3?
Non. Puisque 3 est inférieur à 4, la recherche se concentrera sur la nouvelle moitié inférieure. C'est la deuxième opération principale faite.
La division en deux fait à nouveau fait 2 le nouvel élément moyen.
Est 2 comme 3?
Non. Puisque 3 est supérieur à 2, la recherche se concentrera alors sur la nouvelle moitié supérieure. C'est la troisième opération principale faite.
La division en deux fait à nouveau 3 fait 3 le nouvel élément moyen, d'une demi-liste (sous-liste) de longueur, un. L'article moyen et dernier est maintenant 3.
Est 3 comme 3?
Oui. La valeur cible a été trouvée. C'est la quatrième et dernière opération principale faite.
Lorsqu'il y a 16 articles, un maximum de 4 opérations principales peuvent être effectuées. S'il y avait 16 articles et que la valeur cible était dans la gamme et ne pouvait pas être trouvée, 4 opérations principales auraient encore eu lieu. Par exemple, dans la liste suivante:
1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18Il y a encore 16 articles. Une valeur cible de 3 aurait pris fin à la valeur de 5, avec encore 4 opérations principales.
Complexité du temps et recherche binaire
Performes pires
Les performances les pires cas se réfèrent au cas où la valeur cible se trouve lors de la dernière opération principale, ou la valeur cible est dans la plage de valeurs et ne se trouve pas lors de la dernière opération principale.
Lorsque le nombre d'articles est de 16, le nombre maximum d'opérations sera toujours 4.
16 = 24
4 = journal2(16)
Soit n être 16. Donc,
4 = journal2(n)
Si n est 8, le nombre maximum d'opérations serait 3 = logarithme2(8). Si n est 32, le nombre maximum d'opérations serait de 5 = logarithme2(32).
La complexité temporelle du pire des cas (vitesse relative) pour la recherche binaire serait:
O (journal2(n))
Où le Big O et ses parenthèses ont une bûche2(n) est la notation de la complexité temporelle. Il est simplement écrit comme:
O (log n)
Performance des meilleures cas
Supposons que la valeur cible était de 8 pour la première liste ci-dessus. Dans ce cas, la première opération principale aurait trouvé la position de la valeur cible. C'est la meilleure performance de cas. La complexité du temps pour cette performance des meilleurs cas est écrite comme:
O (1)
Où 1 signifie une opération principale.
Codage en c
Une fonction de recherche binaire de code C est:
#inclureint binararysearch (int arr [], int cible, int n)
int lindex = 0;
int upindex = n - 1;
// Assurez-vous que nous avons encore des éléments dans la liste pour rechercher
while (cible fiindex)
upIndex = middleIndX;
autre
Loindex = middleIndx + 1;
// Renvoie un nombre négatif lorsque nous ne trouvons pas la cible dans le tableau
retour -1;
Le Lindex signifie l'indice le plus bas d'une demi-liste (sous-liste). L'UPIndex signifie l'indice supérieur d'une demi-liste (sous-liste). Au début, Lindex est 0 et Upindex est 15 lorsque N est 16. La condition de boucle while garantit que la division se poursuit jusqu'à ce que Loindex soit le même que Upindex si la valeur cible n'a pas encore été trouvée.
Une fonction principale C appropriée pour ce code est:
int main (int argc, char ** argv)int n = 16;
int cible = 3;
int arr [] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
int indexFound = BinarySearch (arr, cible, n);
printf ("% d \ n", indexfound);
retour 0;
Conclusion
Cet article a discuté de la complexité du temps de recherche binaire et a souligné ce qui suit:
La complexité du temps du pire des cas pour la recherche binaire est:
O (log n)
La complexité du temps de la meilleure cas pour la recherche binaire est:
O (1)