[MIZIK jwe] Doug Lloyd: Lineyè rechèch se yon algorithm nou ka itilize yo jwenn yon eleman nan yon etalaj. Yon rapèl algorithm se yon seri etap-pa-etap nan enstriksyon pou ranpli yon travay. 

Rechèch la lineyè algorithm travay jan sa a. Repekte atravè etalaj la de gòch a dwat, kap chèche yon eleman espesifye. 

Nan pseudocode, ki se yon plis distile vèsyon an fraz sa a, si eleman nan premye se sa w ap chèche pou, ou ka sispann. Sinon, ale nan eleman nan pwochen ak kenbe prale sou yo ak sou jiskaske ou jwenn eleman nan, oswa ou pa fè sa. Se konsa, nou ka sèvi ak lineyè nan algorithm rechèch, pou egzanp, jwenn valè a sib nèf nan etalaj sa a. Oke nou kòmanse nan kòmansman an. Si li nan ki sa nou ap kap chèche, nou ka sispann. Li pa nan, nou ap pa kap chèche 11. Se konsa, otreman, deplase li nan yon eleman kap vini an. 

Se konsa, nou gade nan 23. Se 23 sa nou ap chèche pou? Oke pa gen okenn, se konsa nou deplase sou pwochen an eleman, ak eleman kap vini an, epi nou kenbe ale atravè tout pwosesis sa a sou yo ak sou yo ak sou, jiskaske nou peyi sou yon sitiyasyon tankou sa a. 

Nèf se sa nou ap chèche pou, ak sa a eleman nan etalaj la se, valè li a se nèf. Se konsa, nou jwenn sa nou ap chèche pou yo, epi nou ka sispann. Rechèch la lineyè gen fini, avèk siksè. 

Men, sa ki sou si nou ap chèche pou yon eleman sa a, se pa nan etalaj nou an. Rechèch lineyè toujou travay? Oke asire w. Se konsa, nou repete pwosesis sa a kòmanse nan eleman a an premye. Si li nan ki sa nou ap kap chèche, nou ka sispann. Li pa. Sinon, nou deplase li nan yon eleman kap vini an. 

Men, nou kapab kenbe repete pwosesis sa a, ekzamine chak eleman nan vire, avèk lespwa ke nou jwenn nimewo a 50. Men, nou pa pral konnen si nou te jwenn nimewo a 50 oswa si nou pa t ', jouk nou te te demisyone sou tout eleman sèl nan etalaj la. 

Se sèlman yon fwa nou te fè ki e yo vini ti bout tan, nou ka konkli ke 50 se pa nan etalaj la. Se konsa, rechèch la lineyè algorithm, byen li echwe, se pou chak. Men, pa nan sans ke li te fèt san siksè nan fè sa nou te mande l 'bay fè. 

Li te fèt san siksè nan kòm anpil jan li pa t 'jwenn 50, men 50 pa t 'nan etalaj la. Men, nou te fouye limitativ nan chak eleman sèl e konsa, pandan ke nou pa t 'jwenn anyen, rechèch lineyè toujou reyisi menm si nan eleman se pa nan etalaj la. 

Se konsa, sa ki nan ka ki pi mal senaryo ak rechèch lineyè? Oke nou dwe gade nan chak eleman sèl, swa paske eleman nan sib se eleman ki sot pase a nan etalaj la, oswa eleman nan nou ap chèche pou pa fè sa aktyèlman egziste nan etalaj la nan tout. Ki sa ki nan senaryo a ka pi bon? Oke nou ta ka jwenn nan eleman imedyatman. Ak ki jan anpil eleman nou Lè sa a gen fè yon gade a nan ka a pi bon, si nou ap chèche pou li epi nou jwenn li nan konmansman an anpil? Nou ka sispann imedyatman. 

Ki sa sa di sou la konpleksite nan rechèch lineyè? Byen nan ka ki pi mal, nou gen fè yon gade nan chak eleman sèl. Se konsa, li kouri nan O nan N, nan ka ki pi mal la. 

Nan ka ki pi bon, nou ap pral jwenn eleman nan imedyatman. Se konsa, kouri nan Omega nan 1. 

Mwen se Doug Lloyd. Sa a se CS50.