[Muzikos grojimo] Doug LLOYD: Linijinis paieška algoritmas mes galite naudoti norėdami rasti masyve elementų. Algoritmas Prisiminkite yra žingsnis po žingsnio rinkinys Nurodymų pildymo užduotį. 

Linijinis paieška algoritmas veikia taip. Pakartoti visoje masyvo iš kairės į teisė, ieško tam tikro elemento. 

Be Pseudocode, kuri yra daugiau distiliuotas versija šį sakinį, jei pirmasis elementas yra tai, kas jūs ieškote, jūs galite sustabdyti. Priešingu atveju, pereiti prie kito elemento ir nesustoti daugiau ir daugiau, kol rasite elementas, arba jūs neturite. Taigi, mes galime naudoti tiesinę paieškos algoritmas, pavyzdžiui, rasti siektiną vertę devynių šiame masyve. Na mes pradėti iš pradžių. Jei tai, ką mes ieško, mes galime sustabdyti. Tai ne, mes ne ieško 11. Taigi, kitaip, pereiti prie kito elemento. 

Taigi, mes pažvelgti į 23. Ar 23 ką mes ko ieškote? Na ne, todėl mes pereiti į kitą elementas, ir kitą elementas, ir mes nuolat išgyvena šis procesas vėl ir vėl ir daugiau, kol mes žemę dėl kaip šią situaciją. 

Devyni yra tai, ką mes ieškome, ir šis masyvo elementas yra, tai yra, vertės nėra devyni. Ir todėl mes radome tai, ką mes ieško, ir mes galime sustoti. Linijinis paieška turi baigė sėkmingai. 

Bet ką apie tai, jei mes ieškome elementas, kuris yra ne mūsų masyvo. Ar linijinis paieška vis dar dirba? Na tikrai. Taigi mes kartoti šį procesą pradedant pirmojo elemento. Jei tai, ką mes ieško, mes galime sustabdyti. Tai ne. Priešingu atveju, mes judėti į kitą elementą. 

Tačiau mes galime nuolat kartoti šį procesą, nagrinėja kiekvieną elementą savo ruožtu, tikiuosi, kad mes rasti skaičių 50. Bet mes nežinome, jei mes pastebėjome skaičių 50 arba jei mes padarėme ne, kol mes sustiprino per kiekvieną elementą masyvo. 

Tik tada, kai mes padarėme kad ir sugalvoti trumpas, galime daryti išvadą, kad 50 yra ne masyvo. Ir taip linijinis paieška algoritmas, gerai ji nepavyko, per se. Bet ne ta prasme, kad jį buvo nesėkmingas daryti tai, ką mes paprašėme ją daryti. 

Tai buvo nesėkmingas, nes kiek ji nerado 50, bet 50 buvo ne masyvo. Bet mes turime išsamiai ieškoma per kiekvieną elementą ir taip, o neradome nieko, linijinis paieška vis dar pavyksta, net jei elementas yra ne masyvo. 

Taigi, kas blogiausiu atveju scenarijus su linijiniu paieškoje? Na, mes turime pažvelgti pro kiekvienas elementas, arba todėl, kad tikslinė elementas yra paskutinis elementas masyve, ar elementas mes ieškome ne iš tikrųjų egzistuoja masyvo ne visiems. Koks geriausias scenarijus? Na, mes galime rasti elementas iš karto. Ir kiek elementai mes tada turite ieškoti ne geriausiu atveju, jei mes ieškome jai ir mes rasti pačioje pradžioje? Mes galime nedelsiant nutraukti. 

Ką tai sako apie sudėtingumas tiesinės paieškoje? Na, blogiausiu atveju, mes turime pažvelgti į kiekvieną elementą. Ir todėl jis veikia O N, blogiausiu atveju. 

Geriausiu atveju, mes gonna iš karto rasti elementą. Ir taip eina omega 1. 

AÅ¡ Doug Lloyd. Tai CS50.