[Jouer de la musique] DOUG LLOYD: Linéaire la recherche est un algorithme de nous peut utiliser pour trouver un élément dans un tableau. Un rappel de l'algorithme est un ensemble étape par étape des instructions pour remplir une tâche. 

La recherche linéaire algorithme fonctionne comme suit. Itérer à travers la matrice de gauche à à droite, la recherche d'un élément spécifié. 

Dans pseudo, ce qui est un plus la version distillée de cette phrase, si le premier élément est ce que vous cherchez, vous pouvez vous arrêter. Sinon, passer à l'élément suivant et continuer encore et encore jusqu'à ce que vous trouvez l'élément, ou vous ne le faites pas. Donc, nous pouvons utiliser le linéaire algorithme de recherche, par exemple, pour trouver la valeur cible neuf dans ce tableau. Eh bien, nous commençons par le début. Si elle est ce que nous sommes cherchez, nous pouvons nous arrêter. Il est pas, nous ne sommes pas à la recherche de 11. Donc, autrement, passer à l'élément suivant. 

Donc, nous regardons à 23. Est de 23 ce que nous cherchons? Eh bien non, si nous passons à la prochaine élément, et l'élément suivant, et nous continuons à travers ce processus encore et encore et plus, jusqu'à ce que nous atterrissons sur une situation de ce genre. 

Nine est ce que nous recherchons, et cet élément de la matrice est, sa valeur est de neuf. Et donc nous avons trouvé ce que nous sommes cherchez, et nous pouvons nous arrêter. La recherche linéaire a complété, avec succès. 

Mais qu'en est-il si nous sommes à la recherche un élément qui est pas dans notre tableau. Est-ce que la recherche linéaire fonctionne toujours? Bien sûr. Donc, nous répétons ce processus en commençant par le premier élément. Si elle est ce que nous sommes cherchez, nous pouvons nous arrêter. Ce n'est pas. Sinon, nous passons à l'élément suivant. 

Mais nous ne pouvons continuer à répéter ce processus, examinant chaque élément à son tour, en espérant que nous trouvons le nombre 50. Mais nous ne saurons pas si nous avons trouvé le numéro 50 ou si nous ne l'avons pas, jusqu'à ce que nous avons franchi sur chaque élément du tableau. 

Seulement une fois que nous avons fait cela et trouver à court, pouvons-nous conclure que 50 ne figure pas dans le tableau. Et donc la recherche linéaire algorithme, ainsi il n'a pas, en soi. Mais pas dans le sens où il n'a pas réussi à faire ce que nous lui avons demandé de faire. 

Il a échoué en tant autant qu'il n'a pas trouvé 50, mais 50 ne figurait pas dans le tableau. Mais nous avons exhaustivement recherché à travers chaque élément et ainsi, alors que nous ne l'avons pas trouvé quoi que ce soit, la recherche linéaire encore réussit même si le élément se trouve pas dans le tableau. 

Alors, quel est le pire des cas scénario avec recherche linéaire? Eh bien, nous avons de regarder à travers chaque élément, soit parce que l'élément de cible est le dernier élément du tableau, ou l'élément que nous recherchons ne réellement exister dans le tableau du tout. Quel est le meilleur scénario? Eh bien, nous pourrions trouver le élément immédiatement. Et combien d'éléments avons-nous alors à regarder à dans le meilleur des cas, si nous sommes à la recherche pour elle et nous trouvons au tout début? Nous pouvons cesser immédiatement. 

Qu'est-ce que cela nous dit sur la complexité de la recherche linéaire? Eh bien, dans le pire des cas, nous avons à regarder chaque élément. Et pour qu'il fonctionne dans O n, dans le pire des cas. 

Dans le meilleur des cas, nous allons trouver l'élément immédiatement. Et fonctionne en oméga de 1. 

Je suis Doug Lloyd. Ceci est CS50.