[Prehrávanie hudby] DOUG LLOYD: Linear Vyhľadávanie je algoritmus sme môžete použiť na nájsť prvok v matici. Algoritmus odvolanie je krok-za-krokom set inštrukcií pre dokončenie úlohy. 

Lineárne vyhľadávanie algoritmus pracuje nasledujúcim spôsobom. Iterácii cez pole zľava vpravo, hľadá zadaného prvku. 

V pseudokódu, ktorý je oveľa destilovaná verzia tejto vety, v prípade, že prvý prvok je to, čo hľadáte, môžete zastaviť. V opačnom prípade, presuňte na ďalší prvok a ďalej znovu a znovu, kým nenájdete prvok, alebo nie. Takže môžeme použiť lineárny vyhľadávací algoritmus, napríklad, nájsť cieľovú hodnotu deväť v tomto poli. Tak sme od začiatku. Ak je to to, čo sme hľadáte, môžeme zastaviť. To nie je, že nie hľadáme 11. Takže inak, presuňte na ďalší prvok. 

Takže sa pozrieme na 23 ° C. Je 23 to, čo hľadáme? No nie, tak sme sa presunúť na ďalší prvok, a ďalší prvok, a budeme pokračovať cez tento proces znovu a znovu a znovu, kým sme pristáť na situáciu, ako je táto. 

Deväť je to, čo hľadáme, a tento prvok poľa je, že to je hodnota deväť. A tak sme našli to, čo sme hľadáte, a môžeme zastaviť. Lineárne vyhľadávanie má dokončenie úspešne. 

Ale čo v prípade, že hľadáme prvok, ktorý už nie je v našej poli. Má lineárny hľadanie stále fungovať? No iste. Tak sme tento proces opakovať počnúc prvý prvok. Ak je to to, čo sme hľadáte, môžeme zastaviť. Nie je. Inak sme sa presunúť na ďalší prvok. 

Ale môžeme neustále opakujú tento proces, skúma každý prvok v poradí, dúfať, že nájdeme číslo 50. Ale my, ak nie vedieť, sme našli číslo 50 alebo ak sme nemali, kým ste vstúpil nad každého jednotlivého prvku matice. 

Len raz sme urobili to a prísť krátka, môžeme konštatovať, že 50 nie je v matici. A tak sa lineárny hľadanie algoritmus, dobre to zlyhalo, samo o sebe. Ale nie v tom zmysle, že bol neúspešný v tom, čo Opýtali sme sa ho urobiť. 

To bol neúspešný v as rovnako ako to nenašiel 50, ale 50 nebol v poli. Ale my sme dôkladne prehľadali cez každej jednotlivé súčasti a tak, keď sme nenašli niečo, lineárne hľadanie stále úspešné aj keď element nie je v matici. 

Takže to, čo je najhorší prípad Scenár s lineárnou hľadanie? No musíme prehliadnuť každý prvok, a to buď preto, že cieľový prvok je posledný prvok poľa, alebo prvok hľadáme nie je v poli skutočne existujú vôbec. Aký je najlepší scenár? Tak by sme mohli nájsť prvok okamžite. A koľko prvkov my potom budú musieť hľadať u v najlepšom prípade, ak sa pozeráme na to a my ho nájdeme na začiatku? Môžeme sa okamžite zastaví. 

Čo to hovorí o Zložitosť lineárna hľadanie? No v najhoršom prípade, máme pozrieť sa na každé jednotlivé súčasti. A tak to beží v O. n, v najhoršom prípade. 

V najlepšom prípade, budeme okamžite nájsť prvok. A tak beží v omega 1. 

Som Doug Lloyd. To je CS50.