[TÓNLIST spila] DOUG LLOYD: Línuleg leit er reiknirit við Hægt er að nota til að finna stak í fylki. Reiknirit muna er skref-fyrir-skref sett leiðbeiningar um að ljúka verkefni. 

The línuleg leit reiknirit virkar eins og hér segir. Iterate yfir fylking frá vinstri til rétt, að tiltekinn þáttur. 

Í sauðakóðanum, sem er meira eimað útgáfa af þessari setningu, ef fyrsti þátturinn er það þú ert að leita að, getur þú hættir. Annars, að fara á næsta frumefni og halda áfram aftur og aftur þar til þú finnur þáttur, eða þú hefur ekki. Þannig að við getum notað línulegan leit reiknirit, til dæmis, að finna markgildið níu í þessu fylki. Jæja við byrjum á byrjuninni. Ef það er það sem við erum að leita að, getum við hætt. Það er ekki, við erum ekki að leita að 11. Svo annars, að fara á næsta frumefni. 

Þannig að við lítum á 23. Er 23 það sem við erum að leita að? Jæja nei, svo við fara til the næstur þáttur, og næsta frumefni, og við höldum að fara í gegnum þetta ferli aftur og aftur og aftur, þar til við lendum á aðstæðum eins og þetta. 

Níu er það sem við erum að leita að, og þessi þáttur í fylkinu er það gildi er níu. Og svo við fundum það sem við erum að leita að, og við getum hætt. The línuleg leit hefur lokið, með góðum árangri. 

En hvað um ef við erum að leita að þáttur sem er ekki í fylking okkar. Er línuleg leit vinna enn? Jæja viss. Þannig að við endurtaka þetta ferli byrja á fyrstu frumefni. Ef það er það sem við erum að leita að, getum við hætt. Það er ekki. Annars, hreyfa við á næsta frumefni. 

En við getum halda að endurtaka þetta ferli, skoða hvert frumefni aftur, vona að við finnum fjölda 50. En við munum ekki vita ef við höfum fundið númer 50 eða ef við gerðum ekki, fyrr en við höfum stigið yfir hvert einasta þáttur í array. 

Aðeins þegar við höfum gert sem og að koma upp stutt, við getum gert að 50 er ekki í fylkinu. Og svo línuleg leit reiknirit, vel það tókst ekki, í sjálfu sér. En ekki í þeim skilningi að það var misheppnaður í að gera það spurði við það að gera. 

Það var misheppnaður í eins mikið og það var ekki að finna 50, en 50 var ekki í array. En við höfum tæmandi leitað í gegnum hvert einasta þáttur og svo, á meðan við höfum ekki fundið nokkuð, línuleg leit samt tekst jafnvel þótt þátturinn er ekki í fylkinu. 

Svo er það versta dæmi með línuleg leit? Jæja við verðum að líta í gegnum hvert einasta þáttur, annaðhvort vegna þess að miða þáttur er síðasta þáttur í array, eða þátturinn sem við erum að leita að er ekki í raun fyrir hendi í fylkinu yfirleitt. Hvað er besta falli? Jæja við gætum fundið þáttur strax. Og hversu margir þættir höfum við þá að leita á í besta tilfelli, ef við erum að leita að því og við finnum það í upphafi? Við getum hætt strax. 

Hvað þýðir þetta að segja um flókið línuleg leit? Jæja í versta tilfelli, höfum við að líta á hvert einasta þáttur. Og svo það rennur í O frá n, í versta tilfelli. 

Í besta tilfelli, við erum ađ finna þáttur strax. Og svo keyrir omega af 1. 

Ég er Doug Lloyd. Þetta er CS50.