[Zenelejátszási] DOUG LLOYD: Lineáris keresés egy algoritmus Használhatja találni egy elem a tömbben. Egy algoritmus visszahívás egy lépésről-lépésre sor Az utasítások egy feladat elvégzéséhez. 

A lineáris keresés algoritmus a következőképpen működik. Ismételget az egész tömb balról Rendben, keres egy megadott elem. 

A pszeudokód, amely egy több desztillált változata ez a mondat, ha az első elem az, amit keres, akkor megáll. Ellenkező esetben, lépjen a következő elem és folyamatosan megy újra és újra, amíg meg nem találja az elem, vagy nem. Így tudjuk használni a lineáris keresési algoritmus, például, hogy megtalálják a célérték Kilenc ebben a tömbben. Hát kezdjük az elején. Ha ez az, amit mi keresnek, meg tudjuk állítani. Ez nem, mi nem keres 11. Szóval különben lépjen a következő elem. 

Szóval nézzük 23. 23 amit keresett? Hát nem, így haladunk tovább a következő elemet, és a következő elem, és mi folyamatosan megy keresztül ezt a folyamatot újra és újra és újra, amíg leszállunk egy ilyen helyzetben. 

Kilenc, amit keresünk, és ez az elem a tömb az, hogy ez az érték kilenc. És így találtunk mi vagyunk keresnek, és meg tudjuk állítani. A lineáris keresés rendelkezik befejezett, sikeresen. 

De mi a helyzet, ha keresünk olyan elem, amely nem a tömbben. Vajon lineáris keresés mindig működik? Nos, az biztos. Tehát megismételni ezt a folyamatot kezdve az első elemet. Ha ez az, amit mi keresnek, meg tudjuk állítani. Ez nem. Ellenkező esetben, lépjen a következő elem. 

De mi is folyamatosan ismétlődő ezt a folyamatot, vizsgálata minden elem viszont, remélve, hogy megtaláljuk a szám 50. De nem fogunk tudni, ha találtunk száma 50 vagy ha nem, amíg meg nem lépett alatt minden egyes eleme a tömb. 

Csak egyszer tettünk ezt, és jön létre, rövid, tudjuk következtetni, hogy 50 nem a tömbben. És így a lineáris keresés algoritmust, valamint elmulasztotta, önmagában. De nem abban az értelemben, hogy ez sikertelen volt mit csinál kértük, hogy igen. 

Ez sikertelen volt, mint sokat, mert nem találtam 50, de 50 nem volt a tömbben. De mi kimerítően keresett keresztül minden egyes elem és így, míg nem találtunk semmit, lineáris keresés mindig sikerül is, ha a elem nincs a tömbben. 

Szóval mi a legrosszabb esetben forgatókönyv lineáris keresést? Nos, át kell néznünk Minden egyes eleme, vagy azért, mert a cél elem az utolsó elem a tömb, vagy az elem keresünk nem valóban létezik a tömb egyáltalán. Mi a legjobb esetben? Hát talán megtaláljuk a elem azonnal. És hány elem teszünk utána kell nézni A legjobb esetben, ha keresünk meg és azt látjuk, hogy a kezdet kezdetén? Mi lehet azonnal leáll. 

Mit mond ez a komplexitása lineáris keresés? Nos, a legrosszabb esetben van nézni minden egyes elem. És ez így fut O N, a legrosszabb esetben. 

A legjobb esetben, fogunk megtalálni az elem azonnal. És így fut omegája 1. 

Én Doug Lloyd. Ez CS50.