[Jouer de la musique] 

DOUG LLOYD: Très bien. Donc, la recherche binaire est un algorithme que nous pouvons utiliser de trouver un élément à l'intérieur d'un tableau. Contrairement à la recherche linéaire, il faut une condition spéciale sera réuni à l'avance, mais il est tellement plus efficace si cette condition est, en fait, a rencontré. 

Alors, quelle est l'idée ici? il est diviser pour régner. Nous voulons réduire la taille de la zone de recherche par moitié chaque fois afin de trouver un numéro de cible. Ceci est où cette condition entre en jeu, cependant. Nous ne pouvons que tirer parti de la puissance de l'élimination de la moitié des éléments sans même regarder eux si le tableau est trié. 

Si il est un mélange complet jusqu'à, Nous ne pouvons pas sortir de la main jeter la moitié des éléments, parce que nous ne savons pas ce que nous allons jeter. Mais si le tableau est trié, nous pouvons le faire, parce que nous savoir que tout le à gauche de l'endroit où nous sommes actuellement doit être inférieure à la valeur que nous sommes actuellement à. Et tout à la droit de l'endroit où nous sommes doit être supérieure à la valeur nous sommes en train de regarder. 

Alors, quel est le pseudo- étapes de recherche binaire? Nous répétons ce processus jusqu'à ce que la tableau ou, comme nous procédons à travers, sous-réseaux, des petits morceaux de le tableau original, est de taille 0. Calculer le point médian de la matrice de sous-courant. 

Si la valeur que vous cherchez est dans cet élément du tableau, arrêter. Vous l'avez trouvé. C'est génial. Dans le cas contraire, si la cible est à moins que ce qui est au milieu, si la valeur que nous recherchons pour est inférieure à ce que nous voyons, répéter ce processus, mais changer le point de fin, à la place d'être l'original compléter gamme complète, à être juste à la gauche d'où nous venons d'examiner. 

Nous savions que le milieu était trop élevé, ou la cible est inférieure à la moyenne, et il doit exister, si elle existe à tous les dans le tableau, quelque part à la gauche du point médian. Et donc nous allons mettre le tableau emplacement juste à gauche du milieu en tant que nouveau point de fin. A l'inverse, si la cible est supérieure à ce qui est au milieu, nous faisons exactement la même processus, mais à la place nous changer le point de départ pour être juste à la droite du point central nous vient de calculer. Et puis, on recommence le processus. 

Disons Visualiser cette, OK? Donc, il ya beaucoup de choses, et ici, mais voici un tableau de 15 éléments. Et nous allons garder la trace de beaucoup plus de choses cette fois. Donc, à la recherche linéaire, nous étions juste se soucier de la cible. Mais cette fois, nous voulons soucier où sommes-nous commencer à chercher, où nous arrêtons-nous à la recherche, et ce qui est le point médian de la gamme actuelle. Alors on y va avec la recherche binaire. Nous sommes à peu près bon d'aller, non? Je vais juste de mettre bas ci-dessous ici un ensemble d'indices. Ceci est fondamentalement juste quel élément du tableau dont nous parlons. Avec la recherche linéaire, nous soins, dans la mesure où nous besoin de savoir combien de éléments que nous nous parcourons plus, mais nous ne nous soucions pas vraiment ce élément que nous sommes en train de regarder. En recherche binaire, nous le faisons. Et ce ne sont là là comme un petit guide. 

Donc, nous pouvons commencer, non? Eh bien, pas tout à fait. Se souvenir de ce que je disais à propos de la recherche binaire? Nous ne pouvons pas le faire sur une tableau non trié ou bien, nous ne sommes pas garantir que l' certains éléments ou valeurs ne sont pas accidentellement mis au rebut lorsque nous venons décider d'ignorer la moitié du tableau. 

Donc, la première étape avec une recherche binaire est vous devez avoir un tableau trié. Et vous pouvez utiliser l'un des tri algorithmes dont nous avons parlé pour vous rendre à cette position. Alors maintenant, nous sommes dans une position où nous pouvons effectuer une recherche binaire. 

Donc, nous allons répéter le processus étape par étape et de garder une trace de ce qui se passe que nous allons. Donc, le premier que nous devons faire est de calculer le point médian de la rangée en cours. Eh bien, nous allons dire que nous sommes d'abord tous, à la recherche de la valeur 19. Nous essayons de trouver le numéro 19. Le premier élément de cette tableau est situé à l'indice zéro, et le dernier élément de ce tableau se trouve à l'index 14. Et donc nous allons appeler ceux début et de fin. 

Donc, nous calculons le milieu par ajoutant 0 plus 14 divisé par 2; milieu assez simple. Et nous pouvons dire que le milieu est maintenant 7. Donc, est-ce 15 que nous recherchons? Non ce n'est pas. Nous recherchons 19. Mais nous savons que 19 est plus grande que ce que nous avons trouvé au milieu. 

Donc, ce que nous pouvons faire est changer le point de départ à être juste à droite de la milieu, et de répéter le processus. Et quand nous faisons cela, nous disons maintenant nouveau point de départ est l'emplacement du tableau 8. Ce que nous avons fait est efficace tout ignoré à la gauche de 15. Nous avons éliminé la moitié du problème, et maintenant, au lieu d'avoir à chercher plus de 15 éléments de notre gamme, nous avons seulement à la recherche de plus de 7. Donc 8 est le nouveau point de départ. 14 est toujours le point de fin. 

Et maintenant, nous allons au cours de cette nouveau. Nous calculons le nouveau milieu. 8 plus 14 est 22, divisé par 2 est 11. Est-ce ce que nous recherchons? Non ce n'est pas. Nous recherchons pour une valeur qui est moins de ce que nous venons de trouver. Donc, nous allons répéter le processus à nouveau. Nous allons changer le point de fin être juste à la gauche du point médian. Ainsi, le nouveau point final devient 10. Et maintenant, voilà la seule partie de le tableau que nous avons à trier. Donc, nous avons maintenant éliminé 12 des 15 éléments. Nous savons que si 19 existe dans le tableau, il doit exister quelque part entre l'élément Numéro 8 et l'élément numéro 10. 

Donc, nous calculons de nouveau le nouveau milieu. 8 plus 10 est 18, divisé par 2 est 9. Et dans ce cas, regardez, la cible se trouve au milieu. Nous avons trouvé exactement ce que nous recherchons. Nous pouvons arrêter. Nous avons terminé avec succès une recherche binaire. Bien. Nous savons donc cet algorithme fonctionne si la cible est quelque part à l'intérieur de la matrice. Est-ce que ce travail de l'algorithme si la cible se trouve pas dans la matrice? Eh bien, nous allons commencer ce à nouveau, et cette fois, Voyons pour l'élément 16, qui visuellement nous pouvons voir ne pas exister n'importe où dans le tableau. 

Le point de départ est à nouveau 0. Le point final est à nouveau 14. Ce sont les indices de la première et derniers éléments de la gamme complète. Et nous allons passer par le processus que nous venons a traversé à nouveau, essayer de trouver 16, même si visuellement, nous pouvons déjà dire que ça ne va pas être là. Nous voulons juste vous assurer que cet algorithme sera, en fait, toujours travailler en quelque sorte et pas seulement nous laisser bloqué dans une boucle infinie. 

Alors, quelle est la première étape? Calculer le point médian de la gamme actuelle. Quel est le point médian de la gamme actuelle? Eh bien, il est 7, à droite? 14 plus 0 divisé par 2 est 7. Est de 15 ce que nous cherchons? Non. Il est assez proche, mais nous sommes à la recherche pour une valeur légèrement plus grand que cela. 

Donc, nous savons que ça va être nulle part à la gauche de 15. La cible est supérieure à ce qui est dans le milieu. Et nous avons donc mis le nouveau point de départ pour être juste à la droite du milieu. Le point médian est actuellement de 7, de sorte disons que le nouveau point de départ est de 8. Et ce que nous avons effectivement fait nouveau est ignoré toute la moitié gauche de la matrice. 

Maintenant, nous répétons le traiter une fois de plus. Calculer le nouveau milieu. 8 plus 14 est 22, divisé par 2 est 11. Est de 23 ce que nous cherchons? Malheureusement non. Nous recherchons pour une valeur qui est inférieur à 23. Et dans ce cas, nous allons pour changer le point de fin pour être juste à la gauche du point médian de courant. Le point médian actuel est 11, et donc nous allons définir le nouveau point de fin pour la prochaine fois que nous allons à travers ce processus à 10. 

Encore une fois, nous passons par le processus à nouveau. Calculer le milieu. 8 plus 10 divisé par 2 est 9. Est de 19 ce que nous cherchons? Malheureusement non. Nous sommes toujours à la recherche de un nombre inférieur à cela. Donc, nous allons changer le point de fin pour le moment à être juste à la gauche du point médian. Le point médian est actuellement de 9, de sorte que le point final sera de 8. Et maintenant, nous cherchons simplement en un seul ensemble d'éléments. 

Quel est le point central de ce tableau? Eh bien, il commence à 8, il se termine à 8, le point médian est de 8. Est-ce que ce que nous recherchons? Cherchons-nous 17? Non, nous sommes à la recherche 16. Donc, si elle existe dans la matrice, il doit exister quelque part à gauche de l'endroit où nous sommes actuellement. Alors qu'est-ce qu'on va faire? Eh bien, nous allons mettre le point final d'être juste à la gauche du point médian de courant. Donc, nous allons changer le point de fin à 7. Voyez-vous ce qui vient arrivé ici, bien? Consulter ici maintenant. 

Démarrer est maintenant supérieure à la fin. En effet, les deux extrémités de notre gamme ont traversé, et le point de départ est maintenant, après le point de fin. Eh bien, cela ne veut pas aucun sens, non? Alors maintenant, ce que nous pouvons dire est que nous une matrice de taille sub 0. Et une fois que nous appris à nous ce point, nous pouvons maintenant garantir que l'élément 16 ne pas exister dans la matrice, parce que le point de départ et le point final ont traversé. Et il est donc pas là. Maintenant, notez que ce qui est légèrement différent du point de début et de fin point étant le même. Si nous avions été à la recherche pour 17, il aurait été dans le tableau, et le point de départ et le point de cette dernière itération de fin avant ces points croisés, nous aurions trouvé 17 là. Il est seulement quand ils se croisent que nous pouvons garantir que l'élément ne fonctionne pas exister dans le tableau. 

Prenons donc beaucoup moins étapes que la recherche linéaire. Dans le pire des cas, nous avons eu de diviser une liste de n éléments à plusieurs reprises dans la moitié pour trouver la cible, soit parce que l'élément de cible sera quelque part dans la dernière division, ou il ne existe pas du tout. Ainsi, dans le pire des cas, nous devons diviser les array-- savez-vous? Connexion de n fois; nous avoir à couper le problème dans une moitié certain nombre de fois. Ce nombre de fois est log n. 

Quel est le meilleur scénario? Eh bien, la première nous de temps calculer le milieu, nous trouvons ce que nous cherchons. Dans tous les précédents exemples sur la recherche binaire nous venons tout juste dépassé, si nous avions été à la recherche de l'élément 15, nous aurions trouvé immédiatement. Ce fut dès le début. Ce fut le point médian de la première tentative d'une scission d'une division à la recherche binaire. 

Et si dans le pire cas, la recherche binaire fonctionne dans le journal n, ce qui est nettement mieux de la recherche linéaire, dans le pire des cas. Dans le meilleur des cas, binaire recherche fonctionne en oméga de 1. Donc, la recherche binaire est beaucoup mieux que la recherche linéaire, mais vous avez à traiter avec le processus de le tri d'abord votre réseau avant de pouvoir tirer parti de la puissance de la recherche binaire. 

Je suis Doug Lloyd. Ceci est 50 CS.