Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Lineær søk]
[Patrick Schmid, Harvard University]
[Dette er CS50.] [CS50.TV]
Søking er noe du sannsynligvis gjøre oftere enn du tror.
Selvfølgelig, hver gang du åpner en nettleser
og søk etter en nettside -
eller søk etter vennene dine på din favoritt nettsamfunn -
du søker.
Men det er bare en liten del av søk som du gjør på en daglig basis.
Når du ønsker å finne ut at en blå skjorte i skapet,
eller det perfekte rød bluse for anledningen,
du søker.
Når du går til en butikk som du aldri har vært før,
og du leter etter brokkoli i produserer midtgangen
du søker.
Hva du kan ha begynt å legge merke til
er at avhengig av hva du leter etter
eller hvordan elementene blir organisert når du leter etter dem
det har en effekt på hvordan du søker.
For eksempel, hvis din skjorter henger i skapet,
du kan sikkert bare plukke den ut uten mye leting.
Hvis du antar du har å gå ned midtgangen
å få brokkoli, har du sannsynligvis nødt til å se på alle andre grønnsaker
før du finner ut at brokkoli.
Lineær søk er et eksempel på en slik søker metode - eller algoritme.
Som navnet tilsier,
denne metoden søker etter et element i en lineær måte, den ene etter den andre.
Så, når du ser på resultatene fra din favoritt søkemotor
og du leser nedover resultatlisten,
du bruker lineær søk.
Okay. La oss se på et eksempel.
Si at vi har en liste med tall - 2, 4, 0, 5, 3, 7, 8, og 1 -
og vi leter etter tallet 0.
Selvsagt kan du bare se at 0 er i tredje posisjon.
Men, er et dataprogram ikke så heldig.
Det kan bare "ser" en nummer om gangen.
Så starter i begynnelsen av listen,
det bare "ser" den to.
Programmet kontrollerer så - er 2 lik 0?
Åpenbart ikke. Så det går videre til neste nummer, 4.
Har 4 like 0? Nope.
Den neste, 0. Ah! Null er lik 0..
Der har vi det! Det er i tredje posisjon.
Okay. La oss se på noen pseudokode.
Det er bare et par linjer lange, men la oss se på det en linje av gangen.
Først, la oss definere funksjonen - og vi kommer til å kalle det lineære søk -
og det tar to argumenter - tasten og array.
Nøkkelen er at verdien som vi leter etter,
så i det forrige eksempelet, var at null.
En matrise er en liste med tall
som har alle de verdier som vi kommer til å søke.
Så, hva vi ønsker å gjøre er vi ønsker å se på -
fra alle stillinger, så starter ved begynnelsen av tabellen
Til helt i enden av rekken - slik at lengden i matrisen -
se på hver enkelt stilling og sjekke hver enkelt.
Så det er hva som "for" loop gjør.
Og på hver posisjon, skal vi si
"Er det verdien på det nåværende posisjon lik nøkkel som vi leter etter?"
Så - i det forrige eksempelet igjen, var nøkkelen 0 -
så vi sier "Er matrisen i posisjon lik jeg til null?"
Hvis det er, vi kommer til å returnere 'i' fordi det er den posisjonen vi er på.
Så, i forrige eksempel,
som var den tredje posisjonen.
Hvis vi har gått gjennom hele matrisen
og vi har ikke funnet noe -
så la oss si at vi var ute etter nummer 500
som tydelig ikke var i dette eksemplet -
Vi må tilbake noe,
og vi kommer til å returnere -1.
Og vi bare tilbake -1 fordi det er en posisjon
som ikke finnes i tabellen.
Og så det betyr når du får det tilbake fra en funksjon
det står "Hmm, ok. jeg tror jeg fant ikke noe.
Slik at 500 aldri var der. "
Den fine ting om lineær søk er at
det vil fungere på noen liste over elementer,
uavhengig av hvordan elementene blir bestilt.
Det spiller ingen rolle hvor brokkoli er i produserer midtgangen.
Så lenge du går nedover midtgangen fra begynnelsen til slutten,
du er nødt til å finne den,
forutsatt at butikken ikke har kjørt ut av brokkoli, selvfølgelig.
Men det største styrke er også det største svakhet.
Si du har en liste av to hundre tall
som sorteres 1-200.
Hvis du leter etter antall 198,
du må søke nesten hele listen over numre
før du finner den du leter etter.
Det må være en bedre måte!
Trygg det er.
Men, det er et emne for en annen video.
Også, ikke bekymre deg!
Bare fordi lineær søk er ikke den beste løsningen i alle situasjoner,
det betyr ikke at det ikke kommer i hendig.
Ellers, hvordan ville du finne at brokkoli i produserer midtgangen?
Mitt navn er Patrick Schmid, og dette er CS50.
[CS50.TV]