[MUZIKO Ludante] 

DOUG LLOYD: Bone. Do duuma serĉo estas algoritmo ni povas uzi trovi elementon ene de tabelo. Kontraste lineara serĉo, ĝi postulas speciala kondiĉo esti renkontita antemano, sed estas tiel multe pli efika se ke kondiĉo estas, fakte, renkontis. 

Do kio estas la ideo tie? ĝi estas dividi kaj venki. Ni volas redukti la grandecon de la serĉo spaco por duono ĉiufoje por trovi celan nombron. Jen kie tiu kondiĉo havas rolon, kvankam. Ni povas nur utiligi la povon de forigi duonon de la elementoj sen eĉ rigardi ili se la tabelo estas ordigita. 

Se ĝi estas kompleta miksaĵo supren, Ni ne povas nur el mano forĵeti duonon el la elementoj, ĉar ni ne scias kion ni forĵeti. Sed se la tabelo estas ordigita, ni povas fari tion, ĉar ni scias ke ĉiu al la lasita de kie ni nune estas devas esti pli malalta ol la valoro ni estas nune en. Kaj ĉiu al la rajto de kie ni estas devas esti pli granda ol la valoro ni nuntempe rigardante. 

Do kio estas la _pseudocode_ paŝojn por duuma serĉo? Ni ripeti ĉi procezo ĝis la tabelo aŭ, kiel ni procedas tra, Sub arrays, malgrandaj pecoj de la origina tabelo estas de amplekso 0. Kalkuli la mezpunkto de la aktuala sub tabelo. 

Se la valoro vi serĉas estas en tiu ero de la tabelo, ĉesi. Vi trovis ĝin. Tio estas granda. Alie, se la celo estas malpli ol kio estas en la mezo, do se la valoro ni serĉas cxar estas pli malalta ol kion ni vidas, Ripeti ĉi procezo denove, sed ŝanĝi la fina punkto, anstataŭ esti la originalo kompletigi plena tabelo, esti ĵus maldekstren de kie ni nur rigardis. 

Ni sciis ke la meza havis tro alta, aŭ la celo estis malpli ol la duono, kaj do devas ekzisti, se ĝi ekzistas tute en la tabelo, ie maldekstren de la mezpunkto. Kaj tial ni starigu la tabelo situon ĝuste maldekstren de la mezpunkto kiel nova fina punkto. Male, se la celo estas pli granda ol kio estas en la mezo, ni faru la samajn procezo, sed anstataŭe ni ŝanĝi la komenco punkto esti iom dekstre de la mezpunkto ni simple kalkulas. Kaj tiam, ni komencos la procezon denove. 

Ni bildigi tion, OK? Do ekzistas multe iranta kaj ĉi tie, sed ĉi tie estas tabelo de la 15 elementoj. Kaj ni tuj estos konservanta trako de multaj pli aĵoj ĉi tempo. Do en lineara serĉo, ni estis nur zorgi pri celo. Sed ĉifoje ni volas zorgi pri kie ni estas komencanta rigardi, kie ni haltas rigardanta, kaj kio estas la mezpunkto de la nuna tabelo. Do jen ni iros kun duuma serĉo. Ni estas sufiĉe tre bona iri, ĉu ne? Mi simple tuj meti malsupren sube tie aro de indeksoj. Tiu estas esence nur kion elemento de la tabelo ni parolas. Kun lineara serĉo, ni zorgas, ĉar ni bezonas scii kiom da elementoj ni ripetanta super, sed ni ne vere gravas kio elementon ni aktuale rigardante. En duuma serĉo, ni faros. Kaj tial tiuj estas nur tie kiel malgranda gvidas. 

Do ni povas starti, dekstra? Nu, ne tute. Memoru kion mi diris pri duuma serĉo? Ni ne povas fari ĝin sur unsorted tabelo aux, ni ne garantiante ke la iuj elementoj aŭ valoroj ne esti hazarde forĵetitaj kiam ni ĵus decidas ignori duono de la tabelo. 

Do paŝi unu kun duuma serĉo estas vi devas havi ordo tabelo. Kaj vi povas uzi ajnan el la ordigado algoritmoj ni parolis pri akiri vin al tiu pozicio. Do nun, ni estas en pozicio kie ni povas elfari duuma serĉo. 

Do ni ripeti la procezon paŝon post paŝo kaj teni trako de kio okazas dum ni marŝos. Do la unua ni devas fari estas kalkuli la mezpunkto de la nuna tabelo. Nu, ni diras, ke ni estas, unue ĉiuj, serĉante la valoro 19. Ni provas trovi la nombron 19. La unua elemento de tiu tabelo situas ĉe indeksa nulo, kaj la lasta elemento de tiu tabelo situas ĉe indekso 14. Kaj do ni nomas tiujn komenco kaj fino. 

Do ni kalkuli la mezpunkto de aldonante 0 plus 14 dividite per 2; bela simpla mezpunkto. Kaj ni povas diri ke la mezpunkto estas nun 7. Do estas 15 kion ni serĉas? Ne, ĝi ne estas. Ni serĉas 19. Sed ni scias, ke 19 estas pli granda ol kion ni konstatis en la mezo. 

Do kion ni povas fari estas ŝanĝi la komenco punkto esti iom dekstre de la mezpunkto, kaj ripeti la procezon denove. Kiam ni faras tion, ni nun diru la nova komenco punkto estas tabelo situon 8. Kion ni efektive faris estas ignoris ĉion al la maldekstra de 15. Ni forigas duonon de la problemo, kaj nun, anstataŭ devi serĉi super 15 elementoj en nia tabelo, ni nur devas serĉi pli ol 7. Do 8 estas la nova komenco punkto. 14 estas ankoraŭ la fino punkto. 

Kaj nun ni transiru ĉi denove. Ni kalkulas la nova mezpunkto. 8 plus 14 estas 22 dividita per 2 estas 11. Ĉu tio kion ni serĉas? Ne, ĝi ne estas. Ni serĉas valoron tio malpli ol kion ni ĵus trovis. Do ni tuj ripetas la procezon denove. Ni tuj ŝanĝi la ekstrema punkto por estos precize la maldekstra de la mezpunkto. Do la nova fina punkto iĝas 10. Kaj nun, tio estas la sola parto de la tabelo ni devas ordigi tra. Do ni jam forigita 12 el la 15 elementoj. Ni scias ke se 19 Ekzistas en la tabelo, ĝi devas ekzisti ie inter elemento numero 8 kaj elemento numero 10. 

Do ni kalkulas la nova mezpunkto denove. 8 plus 10 estas 18 dividita per 2 estas 9. Kaj en ĉi tiu kazo, rigardu, la celo estas ĉe la mezo. Ni trovis ĝuste kion ni serĉas. Ni povas haltigi. Ni sukcese kompletigitaj duuma serĉo. Bone. Do ni scias ĉi algoritmo funkcias se la celo estas ie interne de la tabelo. Ĉu tiu algoritmo laboro se la celo ne estas en la tabelo? Nu, ni komencu gxin denove, kaj tiu tempon, ni serĉas la elemento 16, kiu vide povas vidi ne ekzistas ie en la tabelo. 

La komenco punkto estas denove 0. La fina punkto estas denove 14. Tiuj estas la indeksoj de la unua kaj lastaj elementoj de la kompleta tabelo. Kaj ni iros tra la procezo ni ĵus trairis denove, provante trovi la 16 kvankam vide, ni povas jam diru ke ĝi ne tuj estos tie. Ni nur volas certigi tiun algoritmon estos, fakte, ankoraŭ labori iel kaj ne nur lasi nin senmoviĝita en senfina buklo. 

Do kio estas la paŝo unuan? Kalkuli la mezpunkto de la nuna tabelo. Kio estas la mezpunkto de la nuna tabelo? Nu, estas 7, dekstra? 14 Plus 0 dividita per 2 estas 7. Estas 15 kion ni serĉas? No. Ĝi estas sufiĉe proksima, sed ni serĉas por valoro iomete pli granda ol tio. 

Do ni scias, ke ĝi tuj esti nenie maldekstren de 15. La celo estas pli granda ol kio estas en la mezpunkto. Kaj tial ni starigu la nova komenco punkto esti iom dekstre de la mezo. La mezpunkto estas nuntempe 7, do diru la nova komenco punkto estas 8. Kaj kion ni efektive faras: estas ignorataj la tuta maldekstra duono de la tabelo. 

Nun, ni ripetu la procesi pli tempo. Kalkuli la nova mezpunkto. 8 plus 14 estas 22 dividita per 2 estas 11. Estas 23 kion ni serĉas? Bedaŭrinde, ne. Ni serĉas valoron ke estas malpli ol 23. Kaj tiel en tiu kazo, ni tuj ŝanĝi la ekstrema punkto por esti simple maldekstre de la nuna mezpunkto. La nuna mezpunkto estas 11, kaj do ni starigis la nova fina punkto por la venonta fojo ni iros tra ĉi tiu procezo al 10. 

Denove, ni iras tra la procezo denove. Kalkuli la mezpunkto. 8 plus 10 dividita per 2 estas 9. Estas 19 kion ni serĉas? Bedaŭrinde, ne. Ni ankoraŭ serĉas nombro malpli ol tio. Do ni ŝanĝi la ekstrema punkto tiu tempo esti ĵus maldekstren de la mezpunkto. La mezpunkto estas nuntempe 9, tiel la fina punkto estos 8. Kaj nun, ni nur rigardis ĉe ununura elemento tabelo. 

Kio estas la mezpunkto de tiu tabelo? Nu, ĝi komenciĝas ĉe 8, ĝi finiĝas ĉe 8, la mezpunkto estas 8. Ĉu tio kion ni serĉas? Ĉu ni serĉas 17? Ne, ni serĉas 16. Do se ekzistas en la tabelo, ĝi devas ekzisti ie maldekstren de kie ni nune estas. Do kion ni faros? Nu, ni starigis la ekstrema punkto por esti simple maldekstre de la nuna mezpunkto. Do ni ŝanĝi la ekstrema punkto al 7. Ĉu vi vidas kion ĵus okazis tie, kvankam? Rigardu ĉi tien nun. 

Komenci nun pli granda ol fino. Efike, la du flankoj de nia tabelo transiris, kaj la komenco punkto estas nun post la fina punkto. Nu, kiu ne fari neniun senson, dekstra? Do nun, kion ni povas diri estas ni havas sub- tabelo de amplekso 0. Kaj unufoje ni alvenis al tiu punkto, ni povas nun garantii ke elemento 16 Ne ekzistas en la tabelo, ĉar la komenco punkto kaj fina punkto transiris. Kaj tiel ĝi ne estas tie. Nun, rimarki ke tiu estas iomete malsamaj ol la komenco punkto kaj fino atentigi esti la sama. Se ni estus rigardante por 17, ĝi havus estis en la tabelo, kaj la komenco punkto kaj fina punkto de tiu lasta ripeto antaŭ tiuj punktoj transiris, ni estus trovita 17 tie. Ĝi estas nur kiam ili transiras ke ni povas garantii ke la elemento ne ekzistas en la tabelo. 

Do ni multe malpli paŝoj ol lineara serĉo. En la plej malbona kazo scenaro, ni devis fendi liston de n elementoj ree en duono por trovi la celon, ĉu ĉar la celo elemento estos ie en la lasta divido, aŭ ĝi ne ekzistas. Do en la plej malbona kazo, ni devos disigis la tabelo vi scias? Log de n fojojn; ni devos tranĉi la problemon en duono certan nombron da fojoj. Ke plurfoje estas log n. 

Kio estas la plej bona kazo scenaro? Nu, la unuan fojon ni kalkuli la mezpunkto, ni trovos kion ni serĉas. En ĉiuj antaŭaj ekzemploj sur duuma serĉo ni ĵus trapasis, se ni havus estis serĉante la elementon 15, ni trovis ke tuj. Tio estis ĉe la komenco. Tio estis la mezpunkto de la unua provo ĉe escisión de divido en duuma serĉo. 

Kaj tiel en la plej malbona kazo, duuma serĉo kuras en log n, kio estas substance bona ol lineara serĉo, en la plej malbona kazo. En la plej bona kazo, duuma serĉo kuras en omega de 1. Do duuma serĉo estas multe bona ol lineara serĉo, sed vi devas trakti kun la procezo de ordigado via tabelo unue antaŭ vi povas utiligi la povon de duuma serĉo. 

Mi Doug Lloyd. Jen CS 50.