Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Linear Keresés]
[Patrick Schmid, a Harvard Egyetem]
[This Is CS50.] [CS50.TV]
Keres valami, amit valószínűleg nem gyakrabban, mint gondolnád.
Nyilvánvaló, hogy minden egyes alkalommal, amikor megnyit egy webböngészőt
és keressen egy weboldalt -
vagy keressen a barátaidnak a kedvenc social networking site -
keres.
De ez csak egy kis része a keresést, hogy te napi szinten.
Ha azt szeretné, hogy megtalálja, hogy egy kék inget a szekrényben,
vagy hogy tökéletes piros blúz erre az alkalomra,
Ön keres.
Amikor elmész egy boltba, hogy még soha nem volt, hogy korábban,
és keres a brokkoli a termék folyosón
Ön keres.
Amit lehet, kezdett észrevenni
az, hogy attól függően, hogy mit keres
vagy hogyan szervezik az elemeket, amikor keresi őket
ez hatással van, hogyan kereshet.
Például, ha az ing lógott a szekrényben,
akkor valószínűleg csak vedd ki nem sok keresést.
Ha feltételezve, hogy járni a folyosón
, hogy a brokkoli, akkor valószínűleg meg kell nézni az összes többi zöldség
előtt úgy találja, hogy brokkoli.
Lineáris keresés egy példa az egyik ilyen keresés módszer - vagy algoritmus.
Ahogy a neve is mutatja,
ezt a módszert keres egy elemet lineárisan, egyik a másik után.
Tehát, ha keres az eredmények kedvenc keresőprogram
és olvassa le a találati listát,
akkor lineáris keresést.
Oké. Nézzünk egy példát.
Tegyük fel, hogy van egy számlistát - 2, 4, 0, 5, 3, 7, 8, és 1 -
és keresünk a számot 0-ra.
Nyilvánvaló, hogy ha csak látom, hogy a 0 az a harmadik pozícióba.
De, egy számítógépes program nem olyan szerencsés.
Ez csak "látni" egy szám egy időben.
Így, kezdve elején a lista,
csak "látja" a 2.
A program ezután ellenőrzi - a 2 egyenlő 0-ra?
Nyilvánvalóan nem. Így megy ez, hogy a következő szám, 4.
Van 4 egyenlő 0-ra? Nem.
A következő egy, 0. Ah! Nulla egyenlő 0-ra.
Ott van ez! Ez a harmadik pozícióba.
Oké. Nézzünk néhány pszeudokód.
Ez csak egy pár sor hosszú, de nézzük meg, hogy egy sort egy időben.
Először is, nézzük meg a funkciót - és fogunk hívni lineáris keresés -
és két argumentuma - gomb és tömb.
A kulcs az, hogy érték, keresünk,
így az előző példában, ez volt a nulla.
Egy tömb egy listát a számok
hogy az összes értékeket fogunk keresni.
Szóval, mit is akarok, akarunk nézni -
minden pozíciót, így kezdve a legelején a tömb
amíg a legvégén a tömb - így a hossza a tömb -
nézd meg minden egyes helyzetben, és ellenőrizze mindegyik.
Szóval, ez az, ami, hogy a "a" hurok csinál.
És minden helyzetben, fogunk mondani
"Ez érték, hogy a jelenlegi helyzetben egyenlő kulcsot keresünk?"
Így - az előző példában ismét kulcsfontosságú volt 0 -
így mondjuk: "A tömb pozícióban i nullával egyenlő?"
Ha igen, akkor megyünk vissza az "i", mert ez a jelenlegi helyzet már itt tartunk.
Így az előző példában,
ez volt a harmadik pozícióba.
Ha már elment az egész tömb
és már nem talált semmit -
így mondjuk kerestünk a száma 500
ami egyértelműen nem volt a példában -
van vissza valamit,
és megyünk vissza -1.
És mi csak vissza -1, mert ez a helyzet
hogy nem létezik a tömbben.
És ez azt jelenti, ha kap vissza egy függvény
azt mondja: "Hmm, rendben. Azt hiszem, nem találtam semmit.
Szóval, hogy 500 soha nem is volt ott. "
A szép dolog az, hogy a lineáris keresés
Működni fog minden tételjegyzéket,
függetlenül attól, hogy az elemek sorrendben.
Nem számít, ha a brokkoli van a termék folyosón.
Amíg séta a folyosón az elejétől a végéig,
Ön köteles, hogy megtalálja azt,
feltételezve, hogy az üzlet még nem futott ki a brokkoli, természetesen.
De ez a legnagyobb erőssége egyben ez a legnagyobb gyengesége.
Mondja el, hogy van egy lista a 200 szám
vannak rendezve, hogy a 1-200.
Ha keres a szám 198,
meg kell keresni szinte az egész számokat tartalmazó listát
mielőtt megtalálja az egyetlen, amit keres.
Ehhez az kell, hogy legyen egy jobb megoldás!
Biztos lehet benne, hogy van.
De ez a téma egy másik videó.
Továbbá, ne izgulj!
Csak azért, mert a lineáris keresés nem a legjobb megoldás minden helyzetben,
ez nem jelenti azt, hogy nem jól jöhet.
Máskülönben hogyan úgy találja, hogy brokkoli a termék folyosón?
A nevem Patrick Schmid, és ez CS50.
[CS50.TV]