[MUSIC nagpe-play] DOUG LLOYD: De search ay isang algorithm namin ay maaaring gamitin upang mahanap ang isang elemento sa isang array. Isang algorithm recall ay isang step-by-step na set ng mga tagubilin para sa pagkumpleto ng isang gawain. 

Ang haba ng paghahanap algorithm ay gumagana tulad ng sumusunod. Ulitin sa buong array mula kaliwa karapatan, naghahanap para sa isang tinukoy na elemento. 

Sa pseudocode, na kung saan ay isang mas dalisay na bersyon ng pangungusap na ito, kung ang unang elemento ay kung ano ang naghahanap ka ng, maaari mong itigil. Kung hindi man, ilipat sa susunod na elemento at panatilihin ang pagpunta nang paulit-ulit hanggang sa mahanap mo ang elemento, o hindi mo gusto. Kaya maaari naming gamitin ang mga linear algorithm sa paghahanap, halimbawa, upang mahanap ang target na halaga siyam na sa array na ito. Well simulan natin sa simula. Kung ito ay kung ano ang hindi namin naghahanap para sa, maaari naming ihinto. Ito ay hindi, kami ay hindi naghahanap para sa 11. Kaya sa kabilang banda, lumipat sa susunod na elemento. 

Kaya tayo ay tumingin sa 23. Ay 23 kung ano ang namin ang iyong hinahanap? Well no, kaya lumipat kami sa mga susunod na elemento, at ang susunod na sangkap, at panatilihin namin ang pagpunta sa pamamagitan ng ang proseso na ito nang paulit-ulit at higit sa, hanggang sa makarating kami sa isang sitwasyon na ito. 

Siyam ay kung ano ang aming hinahanap, at ito elemento ng array ay, ang halaga na ito ay siyam. At kaya nakita namin kung ano kami naghahanap para sa, at maaari naming ihinto. Ang haba ng paghahanap ay may Matagumpay na natapos,. 

Ngunit ano ang tungkol sa kung kaming naghahanap ng mga isang elemento na hindi sa aming array. Ba linear search pa rin gumagana? Well sigurado. Kaya ulitin namin ang proseso na ito simula sa unang elemento. Kung ito ay kung ano ang hindi namin naghahanap para sa, maaari naming ihinto. Hindi. Kung hindi man, ilipat namin sa susunod na elemento. 

Ngunit maaari naming patuloy na paulit-ulit ang proseso na ito, pagsusuri sa bawat elemento sa turn, umaasa na mahanap namin ang bilang 50. Ngunit hindi namin alam kung nalaman namin ang bilang 50 o kung hindi namin ginawa, hanggang sa na namin stepped sa paglipas ng bawat solong elemento ng array. 

Isang beses lamang ang aming nagawa na iyon at lumapit maikli, maaari naming tapusin na 50 ay wala sa array. At upang ang mga linear paghahanap algorithm, well ito ay nabigo, per se. Ngunit hindi sa kamalayan na ito Hindi naging matagumpay sa paggawa ng kung ano tinanong namin ito upang gawin. 

Ito ay hindi matagumpay sa bilang mas maraming bilang hindi ito mahanap ang 50, ngunit 50 ay wala sa array. Ngunit exhaustively namin ang naghanap sa pamamagitan ng bawat solong elemento at sa gayon, habang kami ay hindi mahanap kahit ano, sa haba ng paghahanap pa rin magtagumpay kahit na ang element ay hindi sa array. 

Kaya kung ano ang pinakamasama kaso senaryo sa linear paghahanap? Well mayroon kaming upang tumingin sa pamamagitan ng bawat solong elemento, alinman dahil ang target element ay ang huling elemento ng array, o ang elemento kaming naghahanap ng mga hindi ang tunay na umiiral sa array sa lahat. Ano ang pinakamahusay na kaso sitwasyon? Well baka makita natin ang element agad. At kung gaano karaming mga elemento huwag pagkatapos kami ay may sa hitsura sa sa pinakamahusay na kaso, kung kami ay naghahanap para sa mga ito at nakita namin ito sa pinakadulo simula? Maaari naming ihinto agad. 

Ano ang ibig sabihin tungkol sa kumplikado ng linear paghahanap? Well sa pinakamasama kaso, kami ay upang tumingin sa bawat solong elemento. At sa gayon ito ay tumatakbo sa O ng n, sa pinakamasama kaso. 

Sa pinakamahusay na kaso, hindi namin gonna mahanap agad ang element. At kaya ay tumatakbo sa wakas ng 1. 

Ako Doug Lloyd. Ito ay CS50.