[Predvaja glasba] Doug LLOYD: Linear Iskanje je algoritem smo lahko uporabite, da bi našli element matrike. Algoritem odpoklic je korak-po-korak set navodil za dokončanje naloge. 

Linearni iskanje Algoritem deluje na naslednji način. Ponovil čez paleto od leve proti Pravica, ki išče določen element. 

V psevdokoda, ki je bolj destilirane različica tega stavka, če je prvi element je tisto iščeš, se lahko ustavite. V nasprotnem primeru, se premaknete na naslednji element in nadaljuj znova in znova, dokler ne boste našli element, ali pa ne. Tako bomo lahko uporabili linearno iskalni algoritem, na primer, najti ciljno vrednost devet v tem polju. No začnemo na začetku. Če je to tisto, kar smo išče moremo ustaviti. Saj ne, ne bomo iskali 11. Torej drugače, se premaknite na naslednji element. 

Torej gledamo na 23. Je 23, kar iščemo? No no, tako da gremo na naslednjo Element, naslednji element, in smo ostali šli skozi ta postopek znova in znova in več, dokler ne bomo pristali o situaciji, kot je ta. 

Devet je tisto, kar smo iskali, in ta element matrike je, da je vrednost je devet. In tako smo ugotovili, kaj smo išče, in ne moremo ustaviti. Linearni iskanje ima končana uspešno. 

Ampak, kaj pa če smo iskali element, ki ga ni v naši matriki. Ali linearno iskanje še vedno deluje? No, seveda. Tako smo ta postopek ponovite izhajajoč iz prvega elementa. Če je to tisto, kar smo išče moremo ustaviti. Ni. Sicer pa smo se premaknete na naslednji element. 

Vendar smo lahko ponavljajo ta proces, preučuje vsak element v zameno v upanju, da bomo našli številko 50. Ampak ne bomo vedeli, če Ugotovili smo številko 50 ali če ne bomo storili, dokler ne bomo stopili več kot vsak element matrike. 

Šele ko smo naredili da in prišli do kratkega, lahko sklepamo, da 50 ni v matriki. In tako linearno iskanje algoritem, tudi to ni uspelo, per se. Vendar ne v smislu, da je ni bila uspešna pri tem, kaj smo ga prosili, da storiti. 

Leta, kot je bila neuspešna toliko, kot je ni našel 50, vendar 50 ni v matriki. Vendar smo izčrpno iskali skozi vsak element in tako, medtem ko nismo našli karkoli, linearno iskanje vedno uspe tudi če Element ni v matriki. 

Torej, kaj je v najslabšem primeru Scenarij z linearnim iskanju? No, moramo odmisliti vsak posamezen element, bodisi zato, ker je ciljna element je zadnji element matrike, ali element, ki ga iščemo ne v matriki pravzaprav sploh obstajajo. Kaj je najboljši scenarij? No, morda bomo našli Element takoj. In koliko elementov bomo potem morali pogledati na v najboljšem primeru Če iščemo zanjo in smo ga našli na samem začetku? Mi lahko takoj ustavi. 

Kaj to povedati o kompleksnost linearne iskanju? No, v najslabšem primeru pa imamo gledati na vsak posamezen element. In tako teče v O n, v najslabšem primeru. 

V najboljšem primeru bomo takoj poiščite element. In tako teče v omega 1. 

Sem Doug Lloyd. To je CS50.