[MUSIC SPILLE] 

DOUG LLOYD: All right. Så binære søk er en algoritme vi kan bruke å finne et element inne i en matrise. I motsetning til lineær søk, det krever en særvilkår bli møtt på forhånd, men det er så mye mer effektiv hvis denne tilstand er faktisk oppfylt. 

Så hva er ideen her? det er splitt og hersk. Vi ønsker å redusere størrelsen på søkeområdet ved halv hver gang for å finne et mål nummer. Det er her at betingelsen kommer inn i bildet, though. Vi kan bare utnytte kraften i å eliminere halvparten av elementene uten å se på dem dersom matrisen er sortert. 

Hvis det er en komplett blanding opp, Vi kan ikke bare ut av hånden forkaste halvparten av elementene, fordi vi vet ikke hva vi skal kastes. Men dersom matrisen sorteres, vi kan gjøre det, fordi vi vet at alt til igjen av hvor vi for tiden er må være lavere enn den verdien vi er nå på. Og alt til høyre for der vi er må være større enn verdien vi for tiden ser på. 

Så hva er pseudo trinn for binære søk? Vi gjentar denne prosessen til matrise eller som vi går gjennom, sub arrays, mindre biter av den opprinnelige matrisen, er av størrelse 0. Beregne midtpunktet av den aktuelle under matrisen. 

Hvis verdien du leter etter er en i det element i matrisen, stopp. Du fant den. Det er flott. Ellers, hvis målet er mindre enn hva som står på midten, så hvis verdien vi leter for er lavere enn det vi ser, gjenta denne prosessen på nytt, men endre sluttpunkt, i stedet av å være den opprinnelige full hel rekke, å være like til venstre hvor vi bare så. 

Vi visste at midten var for høy, eller målet var mindre enn i midten og slik at det må foreligge, hvis det eksisterer i det hele tatt i matrisen, et sted til venstre for midtpunktet. Og så vil vi sette matrisen Beliggenheten like til venstre fra midtpunktet som den nye målpunkt. Omvendt, hvis målet ligger større enn hva som står på midten, vi gjøre akkurat det samme prosessen, men i stedet vi endre startpunktet for å være like til høyre for midtpunktet vi bare beregnet. Og så begynner vi prosessen på nytt. 

La oss visualisere dette, OK? Så det er mye som skjer og på her, men her er et utvalg av de 15 elementene. Og vi kommer til å være å holde styr for en mye mer ting denne gangen. Så i lineær søk, var vi bare bry seg om et mål. Men denne gangen ønsker vi å bryr seg om hvor vi er begynner å se hvor stopper vi ser, og hva som er midtpunktet av den gjeldende matrisen. Så her går vi med binære søk. Vi er ganske mye godt å gå, ikke sant? Jeg bare kommer til å sette ned Nedenfor her et sett av indekser. Dette er i utgangspunktet akkurat det elementet av tabellen vi snakker om. Med lineær søk, vi omsorg, ettersom vi trenger å vite hvor mange elementer vi gjentar løpet, men vi ikke egentlig bryr seg hva element vi for tiden ser på. I binær søk, gjør vi. Og så de er bare der som en liten guide. 

Så vi kan begynne, ikke sant? Vel, ikke helt. Husk hva jeg sa om binære søk? Vi kan ikke gjøre det på en usortert array eller annet, vi er ikke garantere at visse elementer eller verdier ikke er utilsiktet forkastes når vi bare velger å ignorere halvdel av tabellen. 

Så går man med binære søk er at du må ha en sortert array. Og du kan bruke noen av sorterings algoritmer vi har snakket om å få deg til den posisjonen. Så nå er vi i en posisjon der vi kan utføre binære søk. 

Så la oss gjenta prosessen trinn for trinn og holde oversikt over hva som skjer mens vi går. Så det første vi må gjøre er å beregne midtpunktet av den gjeldende matrisen. Vel, vi vil si at vi er først og fremst alle, på jakt etter verdien 19. Vi prøver å finne nummeret 19. Den første del av denne matrise er plassert ved indeks null, og den siste del av denne matrise ligger ved indeks 14. Og så skal vi kalle dem start og slutt. 

Så vi beregne midtpunktet av tilsetning av 0 pluss 14 dividert med 2; ganske grei midtpunktet. Og vi kan si at midtpunktet er nå 7. Så er 15 det vi leter etter? Nei det er det ikke. Vi leter etter 19. Men vi vet at 19 er større enn hva vi fant på midten. 

Så det vi kan gjøre er å endre startpunktet å være akkurat til høyre for midtpunkt, og gjenta prosessen på nytt. Og når vi gjør det, har vi nå si nytt startpunkt er matrise plassering 8. Det vi har effektivt gjort er ignorert alt til venstre for 15. Vi har fjernet halvparten av problemet, og nå, i stedet for å måtte søke over 15 elementer i vår rekke, vi bare nødt til å søke i 7. Så 8 er den nye startpunktet. 14 er fremdeles endepunktet. 

Og nå går vi over denne igjen. Vi beregner den nye midtpunktet. 8 pluss 14 er 22, delt på to er 11. Er det dette vi leter etter? Nei det er det ikke. Vi leter etter en verdi som er mindre enn hva vi fant. Så vi kommer til å gjenta prosessen på nytt. Vi kommer til å endre endepunktet til være like til venstre for midtpunktet. Så den nye endepunktet blir 10. Og nå, det er den eneste delen av matrisen vi må sortere gjennom. Så vi har nå eliminert 12 av de 15 elementene. Vi vet at hvis 19 foreligger i matrisen, det må finnes et sted mellom element nummer åtte og element nummer 10. 

Så vi beregne den nye midtpunktet igjen. 8 pluss 10 er 18, dividert med 2 er 9. Og i dette tilfellet, se den Målet er på midten. Vi fant akkurat det vi leter etter. Vi kan stoppe. Vi fullført et binært søk. Greit. Så vi vet denne algoritmen fungerer hvis målet er et eller annet sted inne i matrisen. Betyr denne algoritmen arbeid hvis målet ikke er i matrisen? Vel, la oss starte det igjen, og denne gangen la oss se for elementet 16, som visuelt kan vi se finnes ikke noe sted i matrisen. 

Startpunktet er igjen 0. Endepunktet er 14 igjen. De er indeksene i første og siste elementer av den fullstendige matrise. Og vi vil gå gjennom prosessen vi bare gikk gjennom på nytt, prøver å finne 16, selv om visuelt, kan vi allerede fortelle at det ikke kommer til å være der. Vi ønsker bare å sørge for denne algoritmen vil faktisk fortsatt arbeid på en eller annen måte og ikke bare la oss fast i en uendelig loop. 

Så hva er det skritt først? Beregne midtpunktet av den gjeldende matrisen. Hva er midtpunktet av den gjeldende matrisen? Vel, det er syv, ikke sant? 14 pluss 0 dividert med 2 er syv. Er 15 det vi leter etter? Nei. Det er ganske nær, men vi ser til en verdi litt større enn det. 

Så vi vet at det kommer til å være noe til venstre for 15. Målet er større enn hva som er i midtpunktet. Og så setter vi det nye startpunktet til være akkurat til høyre for midten. Midtpunktet er for tiden 7, så la oss si den nye startpunktet er åtte. Og det vi har effektivt gjort på nytt blir ignorert hele venstre halvdel av matrisen. 

Nå, vi gjenta behandle en gang til. Beregn den nye midtpunktet. 8 pluss 14 er 22, delt på to er 11. Er 23 det vi leter etter? Dessverre ikke. Vi leter etter en verdi som er mindre enn 23. Og så i dette tilfellet, skal vi å endre sluttpunktet for å være like til venstre for det gjeldende midtpunktet. Den nåværende punktet er 11, og så vi vil sette ny sluttpunktet til neste gang vi går gjennom denne prosessen for å 10. 

Igjen, vi går gjennom prosessen på nytt. Beregne midtpunktet. 8 pluss 10 dividert med 2 er 9. Er 19 det vi leter etter? Dessverre ikke. Vi er fortsatt på jakt etter et tall som er mindre enn det. Så vi kommer til å endre sluttpunktet denne gangen å være like til venstre for midtpunktet. Midtpunktet er for tiden 9, slik at endepunktet vil være åtte. Og nå er vi bare ute ved et enkelt element array. 

Hva er midtpunktet i denne tabellen? Vel, den starter på 8, det slutter ved 8, er midtpunktet 8. Er det det vi leter etter? Er vi på jakt etter 17? Nei, vi leter etter 16. Så hvis det finnes i tabellen, det må finnes et sted til venstre for der vi er nå. Så hva skal vi gjøre? Vel, vi vil sette sluttpunktet for å være like til venstre for det gjeldende midtpunktet. Så vi kommer til å endre sluttpunktet til 7. Ser du hva som nettopp skjedd her, da? Slå opp her nå. 

Start er nå større enn slutten. Vel, de to endene av vår rekke har krysset, og startpunktet er nå etter sluttpunktet. Vel, gjør det ikke gjøre noe fornuftig, ikke sant? Så nå, hva vi kan si er at vi har en sub utvalg av størrelse 0. Og når vi er kommet til dette punktet, kan vi nå garantere at element 16 finnes ikke i tabellen, fordi startpunktet og sluttpunkt har krysset. Og så det er ikke der. Nå, merker at dette er noe annerledes enn startpunkt og slutt punkt er den samme. Hvis vi hadde vært ute til 17, ville det ha vært i matrisen, og startpunktet og sluttpunkt for den siste iterasjon før disse punktene krysset, vi ville ha funnet 17 der. Det er bare når de krysser at vi kan garanterer at elementet ikke finnes i tabellen. 

Så la oss ta en mye mindre trinn enn lineær søk. I verste fall, hadde vi å splitte opp en liste med n elementer gjentatte ganger i to for å finne målet, enten ved at målelementet vil være et sted i den siste divisjon, eller det ikke eksisterer i det hele tatt. Så i verste fall må vi splitte opp array-- vet du det? Logg n ganger; vi må kutte problemet i halv et visst antall ganger. At antall ganger er log n. 

Hva er den best case scenario? Vel, første gang vi beregne midtpunktet, vi finner det vi leter etter. I alle de tidligere eksempler på binære søk Vi har nettopp gått over, hvis vi hadde vært på jakt etter elementet 15, vi ville ha funnet det umiddelbart. Det var helt i begynnelsen. Det var midtpunktet av det første forsøket på en delt av en avdeling i binært søk. 

Og så i verste tilfellet går binære søk i log n, som er vesentlig bedre enn lineær søk, i verste fall. I beste fall, binære søk kjører i omega for en. Så binære søk er mye bedre enn lineær søk, men du har å forholde seg til prosessen med sortering array først før du kan utnytte kraften i binære søk. 

Jeg er Doug Lloyd. Dette er CS 50.