Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Recherche Linéaire]
[Patrick Schmid, Université de Harvard]
[This Is CS50.] [CS50.TV]
La recherche est quelque chose que vous n'avez probablement plus souvent que vous le pensez.
Évidemment, chaque fois que vous ouvrez un navigateur Web
et la recherche d'une page web -
ou la recherche de vos amis sur votre réseau social préféré -
vous recherchez.
Mais ce n'est qu'une petite partie de la recherche que vous faites sur une base quotidienne.
Lorsque vous voulez trouver qu'une chemise bleue dans le placard,
ou ce chemisier rouge parfait pour l'occasion,
vous recherchez.
Lorsque vous allez dans un magasin que vous n'avez jamais été à l'avant,
et vous êtes à la recherche pour le brocoli dans l'allée des produits
vous recherchez.
Qu'est-ce que vous avez commencé à remarquer
c'est en fonction de ce que vous cherchez
ou comment les articles sont organisées lorsque vous êtes à la recherche pour les
il a un effet sur la façon dont vous recherchez.
Par exemple, si vos chemises sont accrochés dans le placard,
vous pouvez probablement le prendre sans beaucoup de recherches.
Si vous partez du principe que vous avez à marcher dans l'allée
pour obtenir le brocoli, vous avez probablement à regarder tous les autres légumes
avant de trouver que le brocoli.
Recherche linéaire est un exemple d'une telle méthode de recherche - ou un algorithme.
Comme son nom l'indique,
cette méthode recherche pour un article d'une manière linéaire, une après l'autre.
Donc, quand vous regardez les résultats de votre moteur de recherche préféré
et que vous lisez en bas de la liste des résultats,
vous utilisez la recherche linéaire.
D'accord. Voyons un exemple.
Disons que nous avons une liste de numéros - 2, 4, 0, 5, 3, 7, 8, et 1 -
et nous recherchons le numéro 0.
Évidemment, il vous suffit de voir que le 0 se trouve dans la troisième position.
Mais, un programme d'ordinateur n'est pas la même chance.
Elle ne peut «voir» un chiffre à la fois.
Donc, à partir du début de la liste,
il ne "voit" le 2.
Le programme vérifie alors - est de 2 égal à 0?
Bien sûr que non. Donc, il va sur le numéro suivant, 4.
Est-ce que 4 0 égaux? Nope.
Le prochain, 0. Ah! Zéro est égal à 0.
Nous y voilà! C'est dans la troisième position.
D'accord. Regardons quelques pseudo-code.
C'est seulement quelques longues lignes, mais regardons les choses d'une ligne à la fois.
Tout d'abord, nous allons définir la fonction - et nous allons l'appeler recherche linéaire -
et il prend deux arguments - clé et tableau.
L'essentiel est que la valeur que nous recherchons,
si dans l'exemple précédent, c'était le zéro.
Un tableau est une liste de numéros
qui a toutes les valeurs que nous allons effectuer la recherche.
Donc, ce que nous voulons faire, c'est que nous voulons regarder -
à partir de toutes les positions, afin de départ au début de la matrice
jusqu'à la fin même de l'ensemble - de sorte que la longueur du tableau -
regardez toutes les positions unique et vérifier chacun.
C'est donc ce que boucle "for" est fait.
Et à chaque position, nous allons dire
"Est-ce que la valeur à cette position courant égal à la clé que nous recherchons?"
Donc - dans l'exemple précédent, la clé était de 0 -
si nous disons: "Est le tableau à la position i égal à zéro?"
Si c'est le cas, nous allons revenir "i" parce que c'est la position actuelle nous en sommes.
Ainsi, dans l'exemple précédent,
qui était la troisième position.
Si nous avons traversé l'ensemble du réseau
et nous n'avons pas trouvé quoi que ce soit -
alors disons que nous recherchions le numéro 500
ce qui n'était clairement pas dans cet exemple -
nous devons retourner quelque chose,
et nous allons renvoyer -1.
Et nous ne faisons que retourner -1 parce que c'est une position
qui n'existe pas dans le tableau.
Et ce qui signifie que lorsque vous récupérez à partir d'une fonction
il dit: "Hmm, ok. Je suppose que je n'ai rien trouvé.
Alors que 500 n'a jamais été là-bas. "
La bonne chose à propos de la recherche linéaire est que
ça va marcher sur une liste d'éléments,
indépendamment de la façon dont les articles sont commandés.
Il n'a pas d'importance où le brocoli est dans l'allée des produits.
Tant que vous marchez dans l'allée du début à la fin,
vous êtes lié pour trouver,
en supposant que le magasin n'a pas manqué de brocoli, bien sûr.
Mais c'est la plus grande force est aussi sa plus grande faiblesse.
Disons que vous avez une liste de deux cents numéros
qui sont classés de 1 à 200.
Si vous cherchez le numéro 198,
il faut chercher presque toute la liste des numéros
avant de trouver celui que vous cherchez.
Il doit y avoir une meilleure façon!
Rassurez-vous il est.
Mais, c'est un sujet pour un autre vidéo.
Aussi, ne vous inquiétez pas!
Tout simplement parce que la recherche linéaire n'est pas la meilleure solution dans toutes les situations,
cela ne signifie pas qu'il ne vient pas en pratique.
Sinon, comment voulez-vous trouver que le brocoli dans l'allée des produits?
Mon nom est Patrick Schmid, et c'est CS50.
[CS50.TV]