[MUZIKO Ludante] DOUG LLOYD: Linear serĉo estas algoritmo ni povas uzi por trovi elementon en tabelo. Algoritmo revokon Estas paŝo-de-paŝo aro de instrukcioj por kompletigado de tasko. 

La lineara serĉo algoritmo laboras kiel sekvas. Persisti trans la tabelo de maldekstre dekstra, rigardante por specifa elemento. 

En _pseudocode_, kiu estas pli distilita versio de tiu frazo, se la unua elemento estas kio vi serĉas, vi povas halti. Alie, movi al la sekva elemento kaj plu iri super kaj trans ĝis vi trovos la elemento, aŭ vi ne faras. Do ni povas uzi linian serĉo algoritmo, ekzemple, trovi la celon valoro naŭ en ĉi tabelo. Nu ni starti je la komenco. Se ĝi estas kio ni estas serĉas, ni povas halti. Ĝi ne estas, ni ne serĉas 11. Do alie, movi al la sekva elemento. 

Do ni rigardu 23. Estas 23 kion ni serĉas? Nu ne, do ni pluiru al la venonta elemento, kaj la sekva elemento, kaj ni plu iri tra ĉi procezo denove kaj denove kaj super, ĝis ni surteriĝi sur tia situacio. 

Naŭ estas kion ni serĉas, kaj ĉi elemento de la tabelo estas, ĝia valoro estas naŭ. Kaj tiel ni trovas kion ni estas serĉas, kaj ni povos halti. La lineara serĉo havas kompletigita, sukcese. 

Sed kio pri se ni serĉas elemento kiu ne estas en nia tabelo. Ĉu lineara serĉo ankoraŭ funkcias? Nu certas. Do ni ripetas ĉi procezo ekde la unua elemento. Se ĝi estas kio ni estas serĉas, ni povas halti. Ĝi ne estas. Alie, ni movi al la sekva elemento. 

Sed ni povas daŭre ripetas ĉi procezo, ekzamenante ĉiu elemento laŭvice, esperante ke ni trovas la numero 50. Sed ni ne scios se ni trovis la nombro 50 aŭ se ni ne faris tion, ĝis ni paŝis super ĉiu unuopa elemento de la tabelo. 

Nur unufoje ni faris tio kaj venis supren mallonga, ni povas konkludi ke 50 Ne en la tabelo. Kaj tial la lineara serĉo algoritmo, bone ĝi malsukcesis, por se. Sed ne en la senco ke ĝi estis malsukcesa en fari kio Ni demandis lin fari. 

Ĝi estis malsukcesa en kiel kiom ĝi ne trovis 50, sed 50 ne estis en la tabelo. Sed ni ĝisfunde traserĉis tra ĉiu ununura ero kaj tial, dum ni ne trovis io, lineara serĉo ankoraŭ sukcesas eĉ se la elemento ne estas en la tabelo. 

Do kio estas la plej malbona kazo scenaro kun lineara serĉo? Nu ni devas rigardi tra ĉiu ununura ero, ĉu ĉar la celo elemento estas la lasta ero de la tabelo, aŭ la elemento ni serĉas ne reale ekzistas en la tabelo ajn. Kio estas la plej bona kazo scenaro? Nu ni povus trovi la elemento tuj. Kaj kiom da elementoj ni tiam devas rigardi ĉe en la plej bona kazo, se ni serĉas ŝin kaj ni trovos ĉe la komenco? Ni povas ĉesi tuj. 

Kion tio diras pri la komplekseco de lineara serĉo? Nu en la plej malbona kazo, ni havas rigardi ĉiu ununura ero. Kaj tiel ĝi kuras en O de n, en la plej malbona kazo. 

En la plej bona kazo, ni estas gonna trovi la elemento tuj. Kaj tiel kuras en omega de 1. 

Mi Doug Lloyd. Jen CS50.