Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Lineaarinen haku]
[Patrick Schmid, Harvardin yliopisto]
[This Is CS50.] [CS50.TV]
Etsiminen on jotain, että et todennäköisesti useammin kuin luulet.
Ilmeisesti aina avata selain
ja etsi Web-sivu -
tai etsi ystäväsi suosikki sosiaalisen verkostoitumisen sivusto -
etsit.
Mutta se on vain pieni osa etsinnän jotka teet päivittäin.
Kun haluat löytää että yksi sininen paita kaapissa,
tai että täydellinen punainen pusero tilaisuutta varten,
etsit.
Kun menet tallentaa joka et ole koskaan ollut ennen,
ja etsit parsakaalin tuottaa käytävällä
etsit.
Mitä olette alkaneet huomata
että riippuen siitä mitä etsit
tai miten kohteet on järjestetty, kun etsit niitä
se vaikuttaa siihen, miten haet.
Esimerkiksi, jos paidat ovat roikkuu kaapissa,
voit todennäköisesti vain noutaa sen pois ilman paljon hakuja.
Jos olet olettaen sinun täytyy kävellä alttarille
saada parsakaali, olet todennäköisesti tarkastella kaikkia muita vihanneksia
ennen kuin huomaat, että parsakaali.
Lineaarinen haku on esimerkki yhdestä tällaisesta hakuja menetelmä - tai-algoritmia.
Kuten nimikin kertoo,
tämä menetelmä hakee kohde lineaarisesti, yksi toisensa jälkeen.
Joten, kun etsit tuloksia suosikki hakukoneen
ja luet alas tulosluettelosta
käytät lineaarista hakua.
Okei. Katsotaanpa esimerkki.
Sanoa, että meidän on luettelo numerot - 2, 4, 0, 5, 3, 7, 8, ja 1 -
ja etsimme numero 0.
Tietenkin voit vain nähdä, että 0 on kolmannella sijalla.
Mutta tietokoneohjelma ei ole niin onnekas.
Se voi vain "näkee" yksi numero kerrallaan.
Niin, alusta alkaen luettelon,
se vain "näkee" 2.
Ohjelma tarkistaa sitten - on 2 yhtä suuri kuin 0?
Ilmeisesti ei. Niin se menee seuraavaan numeroon, 4.
Onko 4 yhtä 0? Nope.
Seuraava, 0. Ah! Zero on yhtä suuri kuin 0.
Siellä meillä on! Se on kolmanneksi.
Okei. Katsotaanpa joitakin pseudokoodilla.
Se on vain pari riviä pitkä, mutta katsotaanpa se yksi rivi kerrallaan.
Ensimmäinen, nyt määritellä funktio - ja aiomme kutsua sitä lineaarinen haku -
ja se kestää kaksi argumenttia - avain ja valikoima.
Tärkeintä on, että arvo etsimme,
joten edellisessä esimerkissä, se oli nolla.
Array on numeroiden luettelosta
että on kaikki arvot, jotka aiomme etsiä.
Joten, mitä haluamme tehdä, on me haluamme tarkastella -
kaikista asemista, joten alkaen alusta array
til aivan loppuun array - niin pituuden array -
tarkastella jokaisen asennossa ja tarkista jokainen.
Niin, että mitä se "for" silmukka tekee.
Ja jokaisessa asennossa, aiomme sanoa
"Onko se arvo, että nykyinen sijainti sama avain että etsimme?"
Joten - edellisessä esimerkissä taas avain oli 0 -
niin sanomme "Onko array asemassa i nolla?"
Jos se on, me aiomme palata "i", koska se on nykyisen sijainnin me olemme.
Niin, että edellisessä esimerkissä,
, joka oli kolmannessa asennossa.
Jos olemme käyneet läpi koko joukko
emmekä ole löytäneet mitään -
niin sanotaan etsimme numero 500
joka ei selvästikään ollut, että esimerkiksi -
Meidän on palattava jotain,
ja aiomme palata -1.
Ja me vain palata -1 koska se kantaa
että ei ole olemassa jono.
Ja niin se tarkoittaa, kun saat sen takaisin toiminto
se sanoo "Hmm, okei. kai en löytänyt mitään.
Niin, että 500 ei koskaan ollut siellä. "
Kiva juttu lineaarinen haku on, että
se täytyy harjoitella kaikkia luettelon kohteita,
riippumatta siitä, miten tuotteet tilataan.
Sillä ei ole väliä missä parsakaali on tuottaa käytävällä.
Niin kauan kuin voit kävellä käytävää pitkin alusta loppuun,
olet varmasti löytää sen,
olettaen myymälä ei lopu parsakaalia, tietenkin.
Mutta suurin vahvuus on myös se suurin heikkous.
Sano sinulla on luettelon kaksisataa numeroa
että lajitellaan 1-200.
Jos etsit numero 198,
sinun täytyy etsiä lähes koko listan numerot
ennen kuin löytää yhden olet etsimässä.
On oltava parempi tapa!
Voit olla varma on.
Mutta se aihe toinen video.
Myös, ei tuskailla!
Vain koska lineaarinen etsintä ei ole paras ratkaisu kaikissa tilanteissa,
se ei tarkoita, että se ei ole tullut kätevä.
Muuten, miten huomaat, että parsakaali on tuottaa käytävällä?
Nimeni on Patrick Schmid, ja tämä on CS50.
[CS50.TV]