Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Lineārā meklēšana]
[Patrick Schmid, Hārvarda universitātes]
[Tas ir CS50.] [CS50.TV]
Meklēšana ir kaut kas jums, iespējams darīt biežāk, nekā jūs domājat.
Acīmredzot, katru reizi atverot savu tīmekļa pārlūkprogrammu
un meklēt mājas lapā -
vai meklēt saviem draugiem par savu iecienītāko sociālo tīklu vietnē -
Jūs meklējat.
Bet tas ir tikai neliela daļa no meklēšanas, kas jums jādara katru dienu.
Ja jūs vēlaties, lai atrastu, ka viena zilā kreklā skapī,
vai ka ideāls sarkana blūze par godu,
jūs meklējat.
Kad jūs doties uz veikalu, ka jūs nekad neesmu bijis pirms,
un jūs meklējat brokoļiem ražot ejā
jūs meklējat.
Ko jūs varētu būt sākuši pamanīt
ir tas, ka atkarībā no tā, ko jūs meklējat
vai kā preces tiek organizēts, kad jūs meklējat tiem
tas ir ietekme uz to, kā jūs meklēt.
Piemēram, ja jūsu krekli ir karājas skapī,
Jūs varat droši vienkārši paņemt to veic bez daudz meklēšanu.
Ja jūs pieņemot, ka jums ir staigāt pa eju
lai iegūtu brokoļus, jūs, iespējams, ir jāskatās uz visām citiem dārzeņiem
Pirms jūs atradīsiet, ka brokoļi.
Lineārā meklēšana ir piemērs šādai meklējot metodes - vai algoritmu.
Kā norāda nosaukums,
šī metode meklē vienuma lineāri, viens pēc otra.
Tātad, ja jūs meklējat pie no jūsu mīļākie meklētājprogrammu rezultātu
un jūs lasīt leju rezultātu sarakstu,
Jūs izmantojat lineāro meklēšanu.
Labi. Apskatīsim piemēru.
Teikt, mums ir saraksts ar numuriem - 2, 4, 0, 5, 3, 7, 8, 1 un -
un mēs meklējam skaitlis 0.
Protams, jūs varat vienkārši redzēt, ka 0 ir trešajā pozīcijā.
Bet, datorprogramma nav tik paveicies.
To var tikai "redzēt" viens numurs laikā.
Tātad, sākot sā***ā saraksta,
tas tikai "redz" 2.
Programma tad pārbauda - ir 2 vienāds ar 0?
Acīmredzot ne. Tā tas notiek uz nākamo numuru, 4.
Vai 4 vienādās 0? Nope.
Nākamais, 0. Ah! Nulle ir vienāds ar 0.
Tur mums ir tā! Tas ir trešajā pozīcijā.
Labi. Apskatīsim kādu pseudocode.
Tas ir tikai pāris līnijas ilgi, bet pieņemsim apskatīt to vienu līniju laikā.
Pirmkārt, pieņemsim definēt funkciju - un mēs ejam, lai izsauktu to lineāra meklēšana -
un tas aizņem divus argumentus - atslēgu un masīvs.
Galvenais ir, ka vērtība, ko mēs meklējam,
tāpēc iepriekšējā piemērā, ka bija nulle.
Masīvs ir saraksts ar numuriem
kas ir visas vērtības, ka mēs ejam, lai meklētu.
Tātad, ko mēs vēlamies darīt, ir, mēs vēlamies apskatīt -
no visām pozīcijām, tāpēc sākot pašā sā***ā masīva
til pašām beigām masīva - tā garumu masīva -
apskatīt katru pozīciju un pārbaudīt katru vienu.
Tātad, tas ko, ka "par" cilpa dara.
Un katrā pozīcijā, mēs esam gatavojas teikt
"Vai šī vērtība šajā pašreizējā stāvoklī ir vienāds ar atslēgu, kas mēs esam meklējat?"
Tātad - iepriekšējā piemērā atkal, galvenais bija 0 -
tāpēc mēs sakām: "Vai, vai masīva pie pozīcijai i vienāds ar nulli?"
Ja tā ir, mēs ejam, lai atgrieztos "i", jo tas ir pašreizējais stāvoklis, mēs esam pie.
Tātad, iepriekšējā piemērā,
kas bija trešajā pozīcijā.
Ja mēs esam izgājuši cauri visam blokam
un mēs esam nav atrasts neko -
tāpēc pieņemsim, ka mēs meklējam skaitu 500
kas acīmredzami nebija šajā piemērā -
Mums ir jāatgriežas kaut ko,
un mēs esam gatavojas atgriezties -1.
Un mēs esam tikai atgriežas -1, jo tas ir amats
ka nepastāv masīvā.
Un tāpēc tas nozīmē, ja jums to atpakaļ no funkciju
tā saka: "Hmm, labi. es domāju, es neatradu neko.
Tā savu 500 nekad nav bijis tur. "
Jauka lieta par lineāru meklēšana ir tas, ka
tas būs strādāt ar jebkuru pozīciju sarakstu,
neatkarīgi no tā, cik preces ir pasūtīts.
Tas nav svarīgi, ja brokoļi ir ražot ejā.
Kamēr jūs staigāt pa eju no sākuma līdz beigām,
Jūs noteikti atradīsiet to,
pieņemot veikalu nav beigušies brokoļi, protams.
Bet tas ir lielākais spēks ir arī tas ir lielākais vājums.
Say jums ir saraksts divsimt numurus
kas ir sakārtoti 1-200.
Ja jūs meklējat numuru 198,
Jums ir meklēt gandrīz visu sarakstu numuru
Pirms jums atrast vienu jūs meklējat.
Ir jābūt labāks veids!
Esiet pārliecināti, ka ir.
Bet, tas ir jautājums par citu video.
Tāpat, nav fret!
Tikai tāpēc, ka lineārs meklēšana nav labākais risinājums visās situācijās,
tas nenozīmē, ka tas nav noderēs.
Pretējā gadījumā, kā jūs atradīsiet, ka brokoļiem ražot ejā?
Mans vārds ir Patrick Schmid, un tas ir CS50.
[CS50.TV]