[Musik spiller] 

DOUG LLOYD: Okay. Så binær søgning er en algoritme vi kan bruge at finde et element inde i et array. I modsætning til lineær søgning, men det kræver en særlige betingelse være opfyldt på forhånd, men det er så meget mere effektiv, hvis denne betingelse er faktisk opfyldt. 

Så hvad er ideen her? det er kløft og erobre. Vi ønsker at reducere størrelsen af søgeområdet med halvdelen hver gang med henblik på at finde en destinationsnummer. Det er her, denne betingelse kommer i spil, selv om. Vi kan kun udnytte kraften i fjerne halvdelen af ​​elementerne uden selv at se på dem, hvis array sorteres. 

Hvis det er en komplet blanding op, Vi kan ikke bare ud af hånden skille halvdelen af ​​elementerne, fordi Vi ved ikke, hvad vi kassere. Men hvis arrayet er sorteret, vi kan gøre det, fordi vi ved, at alt til tilbage af, hvor vi i øjeblikket er skal være lavere end den værdi, vi er her på. Og alt til ret til, hvor vi er skal være større end værdien vi i øjeblikket kigger på. 

Så hvad er pseudokode trin for binær søgning? Vi gentager denne proces, indtil den matrix eller, som vi fortsætte gennem, sub arrays, mindre stykker den oprindelige matrix, er størrelse 0. Beregn midtpunktet af den nuværende sub-array. 

Hvis den værdi, du leder efter i denne del af matrixen, stop. Du fandt den. Det er godt. Ellers, hvis målet er mindre end, hvad der er i midten, så hvis den værdi, vi leder efter for er lavere end det, vi ser, gentage denne proces igen, men ændre slutpunktet, i stedet for at være den oprindelige fuldføre fuld array, at være lige til venstre af, hvor vi lige har set. 

Vi vidste, at den midterste var for høj, eller målet var mindre end i midten, og det skal eksistere, hvis det overhovedet eksisterer i arrayet, et sted til venstre for midten. Og så vil vi sætte array placering lige til venstre af midtpunktet som den nye slutpunkt. Omvendt, hvis målet er større end, hvad der er i midten, vi gør præcis de samme proces, men i stedet vi ændre startpunktet at være lige til højre for midtpunktet vi netop beregnet. Og så begynder vi processen igen. 

Lad os visualisere det, OK? Så der er en masse i gang, og her, men her er en række af de 15 elementer. Og vi kommer til at holde styr af en masse flere ting denne gang. Så i lineær søgning, vi var bare bekymre sig om et mål. Men denne gang vil vi bekymrer sig om hvor er vi begynder at se, hvor stopper vi ser, og hvad er midtpunktet af den nuværende array. Så her går vi med binær søgning. Vi er temmelig meget god til at gå, ikke? Jeg bare at sætte ned nedenfor her et sæt af indekser. Dette er dybest set lige hvad element af array, vi taler om. Med lineær søgning, vi pleje, idet vi brug for at vide, hvor mange elementer vi iteration løbet, men vi ved ikke faktisk pleje, hvad element vi i øjeblikket kigger på. I binær søgning, gør vi. Og så dem er blot der som en lille guide. 

Så vi kan begynde, ikke? Nå, ikke helt. Husk, hvad jeg sagde om binær søgning? Vi kan ikke gøre det på en usorteret matrix eller andet, vi er ikke garanti for, at den visse elementer eller værdier ikke utilsigtet kasseres, når vi blot beslutte at ignorere halvdelen af ​​arrayet. 

Så trin en med binær søgning er du skal have et ordnet array. Og du kan bruge nogen af ​​sorteringen algoritmer vi har talt om at få dig til denne stilling. Så nu er vi i en position, hvor Vi kan udføre binær søgning. 

Så lad os gentage processen trin for trin og holde styr på, hvad der sker, når vi går. Så det første, vi skal gøre, er at beregne midtpunktet af det aktuelle array. Nå, vil vi sige, vi er først og alle, på udkig efter værdien 19. Vi forsøger at finde nummeret 19. Det første element i denne array er placeret ved indeks nul, og det sidste element i denne array er placeret ved indeks 14. Og så vi vil kalde dem, start og slut. 

Så vi beregner midtpunktet af tilføjer 0 plus 14 divideret med 2; temmelig ligetil midtpunkt. Og vi kan sige, at midtpunktet er nu 7. Så er 15, hvad vi leder efter? Nej, det er ej. Vi leder efter 19. Men vi ved, at 19 er større end hvad vi findes på midten. 

Så det, vi kan gøre, er ændre startpunktet at være lige til højre for midtpunktet, og gentage processen igen. Og når vi gør det, vi nu siger den ny start punkt er vifte placering 8. Hvad vi har reelt gjort, er ignoreret alt til venstre for 15. Vi har fjernet halvdelen af problemet, og nu, i stedet for at skulle søge over 15 elementer i vores array, vi kun nødt til at søge over 7. Så 8 er det nye startpunkt. 14 er stadig slutpunktet. 

Og nu, vi gå over det igen. Vi beregner den nye midtpunkt. 8 plus 14 er 22 divideret med 2 er 11. Er det, hvad vi leder efter? Nej, det er ej. Vi leder efter en værdi, der er mindre end hvad vi lige har fundet. Så vi kommer til at gentage processen igen. Vi kommer til at ændre slutpunktet til være lige til venstre for midten. Så den nye slutpunktet bliver 10. Og nu, det er den eneste del af array vi nødt til at gå igennem. Så har vi nu elimineret 12 af de 15 elementer. Vi ved, at hvis 19 findes i arrayet, det skal eksistere et sted mellem element nummer 8 og element nummer 10. 

Så vi beregne nye midtpunktet igen. 8 plus 10 er 18 divideret med 2 er 9. Og i dette tilfælde, ser det Målet er på midten. Vi fandt præcis, hvad vi leder efter. Vi kan stoppe. Vi fuldført en binær søgning. Okay. Så vi ved denne algoritme virker, hvis målet er et sted inde i grupperingen. Er denne algoritme arbejde, hvis målet er ikke i array? Nå, lad os starte det igen, og denne gang, lad os se efter elementet 16, som visuelt kan vi se findes ikke overalt i arrayet. 

Startpunktet er igen 0. Slutpunktet er igen 14. Det er de indekser i den første og sidste elementer i komplet vifte. Og vi vil gå igennem den proces, vi bare gik igennem igen, forsøger at finde 16, selvom visuelt, kan vi allerede fortælle, at det ikke kommer til at være der. Vi ønsker blot at sikre, at denne algoritme vil i virkeligheden stadig arbejde på en eller anden måde og ikke bare lade os fast i en uendelig løkke. 

Så hvad er skridt først? Beregn midtpunktet af den nuværende array. Hvad er midtpunktet af den nuværende array? Tja, det er 7, ikke? 14 plus 0 divideret med 2 er 7. Er 15, hvad vi leder efter? Nej. Det er temmelig tæt, men vi leder efter til en værdi lidt større end det. 

Så vi ved, at det kommer til at være ingenting til venstre for 15. Målet er større end hvad der er i midtpunktet. Og så satte vi den nye start punkt til være lige til højre for midten. Midtpunktet er i øjeblikket 7, så lad os sige den nye start punkt er 8. Og hvad vi har reelt gjort igen ignoreres hele venstre halvdel af arrayet. 

Nu gentager vi den behandle endnu en gang. Beregn den nye midtpunkt. 8 plus 14 er 22 divideret med 2 er 11. Er 23, hvad vi leder efter? Desværre ikke. Vi leder efter en værdi der er mindre end 23. Og så i dette tilfælde, vil vi at ændre slutpunktet at være lige til venstre for den aktuelle midtpunktet. Den nuværende midtpunktet er 11, og så vi vil sætte den nye slutpunkt til næste gang vi gå gennem denne proces til 10. 

Igen, vi gå gennem processen igen. Beregn midtpunktet. 8 plus 10 divideret med 2 er 9. Er 19, hvad vi leder efter? Desværre ikke. Vi er stadig på udkig efter et tal mindre end det. Så vi vil ændre slutpunktet denne gang at være lige til venstre for midten. Midtpunktet er i øjeblikket 9, så slutpunktet bliver 8. Og nu er vi bare at kigge på et enkelt element array. 

Hvad er midtpunktet af dette array? Tja, det starter ved 8, det slutter ved 8, midtpunktet er 8. Er det det, vi leder efter? Søger vi 17? Nej, vi leder efter 16. Så hvis den findes i arrayet, Det skal findes et andet sted til venstre for hvor vi i øjeblikket er. Så hvad skal vi gøre? Nå, vil vi angive slutpunktet for at være lige til venstre for den aktuelle midtpunktet. Så vi vil ændre slutpunktet til 7. Kan du se, hvad der lige skete her, selvom? Kig op her nu. 

Start nu større end ende. Effektivt, de to ender af vores matrix har krydset, og startpunktet er nu efter slutpunktet. Nå, der ikke nogen mening, ikke? Så nu, hvad vi kan sige, er vi har en sub vifte af størrelse 0. Og når vi er kommet til dette punkt, kan vi nu sikre, at element 16 findes ikke i arrayet, fordi startpunktet og slutpunkt har krydset. Og så det er der ikke. Nu bemærke, at det er en anelse anderledes end startpunktet og slutningen peger være det samme. Hvis vi havde været leder til 17, ville det have været i arrayet, og startpunktet og slutpunkt for den sidste iteration før disse punkter krydses, vi ville have fundet 17 der. Det er kun, når de krydser, at vi kan sikre, at elementet ikke findes i arrayet. 

Så lad os tage en masse færre trin end lineær søgning. I værste fald, havde vi at splitte en liste over n elementer flere gange i halvdelen at finde målet, enten fordi måldelen vil være et sted i den sidste division, eller det findes ikke på alle. Så i værste fald er vi nødt til opdele de array-- kender du? Log af n gange; vi nødt til at skære problemet i et halvt bestemt antal gange. Det antal gange, er log n. 

Hvad er den bedste tænkelige scenarie? Nå, første gang vi beregne midtpunktet, finder vi, hvad vi leder efter. I alle de foregående eksempler på binær søgning vi har netop gået over, hvis vi havde været på udkig efter elementet 15, vi ville have fundet det samme. Det var i begyndelsen. Det var midtpunktet af det første forsøg på en split af en division i binær søgning. 

Og så i værste tilfælde binær søgning kører i log n, som er væsentligt bedre end lineær søgning, i værste fald. I bedste fald binære søgning kører i omega på 1. Så binær søgning er meget bedre end lineær søgning, men du er nødt til at beskæftige sig med processen med sortering dit array først, før du kan udnytte kraften i binær søgning. 

Jeg er Doug Lloyd. Dette er CS 50.