Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Linjär sökning]
[Patrick Schmid, Harvard University]
[Detta är CS50.] [CS50.TV]
Sökning är något som du förmodligen göra oftare än du tror.
Självklart, varje gång du öppnar en webbläsare
och söka efter en webbsida -
eller sök efter dina vänner på din favorit sociala nätverk -
du söker.
Men det är bara en liten del av sökandet som du gör på en daglig basis.
När du vill hitta det en blå skjorta i garderoben,
eller den perfekta röda blus för tillfället,
du söker.
När du går till en butik som du aldrig har varit i förut,
och du letar efter broccolin i producera gången
du söker.
Vad du kanske har börjat märka
är det beroende på vad du letar efter
eller hur objekten ordnas när du letar efter dem
det har en effekt på hur du söker.
Till exempel, om dina skjortor hänger i garderoben,
Du kan förmodligen bara plocka ut det utan mycket letande.
Om du antar att du har att gå ner i gången
att få broccoli, har du förmodligen att titta på alla andra grönsaker
innan du upptäcker att broccoli.
Linjär Search är ett exempel på en sådan sökning metod - eller algoritm.
Som namnet antyder,
denna metod söker efter ett objekt i ett linjärt sätt, den ena efter den andra.
Så när du tittar på resultaten från en sökmotor
och du läser nedåt i listan över resultat,
du använder linjär sökning.
Okej. Låt oss titta på ett exempel.
Säga att vi har en lista med tal - 2, 4, 0, 5, 3, 7, 8, och 1 -
och vi letar efter numret 0.
Självklart kan du bara se till att 0 är i den tredje positionen.
Men är ett datorprogram inte så lyckligt lottade.
Det kan bara "se" en siffra i taget.
Så, med start i början av listan,
det bara "ser" 2.
Programmet kontrollerar då - är 2 lika med 0?
Uppenbarligen inte. Så det går vidare till nästa nummer, 4.
Har 4 lika 0? Nix.
Nästa, 0. Ah! Noll är lika med 0.
Där har vi det! Det är i den tredje positionen.
Okej. Låt oss titta på några pseudokod.
Det är bara ett par rader lång, men låt oss titta på det en rad i taget.
Först, låt oss definiera funktionen - och vi kommer att kalla det linjära sökning -
och det tar två argument - nyckel och matris.
Det viktiga är att värde som vi letar efter,
så i föregående exempel, var att noll.
En array är en lista med tal
som har alla de värden som vi kommer att söka.
Så, vad vi vill göra är att vi vill titta på -
från alla positioner, så startar vid början av uppsättningen
til slutet av arrayen - så längden på arrayen -
titta på varje enskild position och kontrollera var och en.
Så det är vad som "för" loop gör.
Och vid varje position, kommer vi att säga
"Är det värde på den aktuella positionen är lika med nyckeln som vi letar efter?"
Så - i föregående exempel igen, var nyckeln 0 -
så vi säger "Är matrisen vid position jag lika med noll?"
Om det är, vi kommer att återvända "i" eftersom det är den aktuella positionen vi är på.
Så, i föregående exempel,
som var den tredje positionen.
Om vi har gått igenom hela matrisen
och vi har inte hittat något -
så låt oss säga att vi letade efter numret 500
som tydligt inte i detta exempel -
Vi måste återvända något,
och vi kommer att återvända -1.
Och vi bara tillbaka -1 eftersom det är en position
som inte existerar i arrayen.
Och så det betyder när du får den tillbaka från en funktion
det står "Hmm, okej. Jag antar att jag inte hittade något.
Så att 500 var aldrig där. "
Det fina med linjär sökning är att
det ska fungera på någon lista över objekt,
oavsett hur objekten beställs.
Det spelar ingen roll om broccoli är i producera gången.
Så länge du gå ner i gången från början till ***,
du är tvungen att hitta det,
förutsatt att butiken inte har *** på broccoli, förstås.
Men det största styrka är också dess största svaghet.
Säg att du har en lista med 200 nummer
som är sorterade från 1 till 200.
Om du letar efter numret 198,
du måste söka nästan hela listan med siffror
innan du hittar en du letar efter.
Det måste finnas ett bättre sätt!
Lita finns.
Men det är ett ämne för en annan video.
Dessutom, oroa dig inte!
Bara för att linjär sökning är inte den bästa lösningen i alla situationer,
Det betyder inte att det inte komma till hands.
Annars, hur skulle du finna att broccoli i producera gången?
Mitt namn är Patrick Schmid, och detta är CS50.
[CS50.TV]