[MUSIK SPELA] 

DOUG LLOYD: Okej. Så binär sökning är en algoritm kan vi använda att hitta ett element inne i en matris. Till skillnad från linjär sökning, krävs det en särskilda villkor måste uppfyllas på förhand, men det är så mycket mer effektivt om detta villkor är faktiskt uppfyllda. 

Så vad är tanken här? Det är söndra och härska. Vi vill minska storleken på sökområdet med hälften varje gång i syfte att finna ett målnummer. Det är där detta villkor kommer in i bilden, men. Vi kan bara utnyttja kraften i eliminera hälften av elementen utan att ens titta på dem om arrayen sorteras. 

Om det är en komplett blandning upp, vi kan inte bara ur hand kassera hälften av elementen, eftersom vi vet inte vad vi ska kasta. Men om matrisen är sorterad, vi kan göra det, eftersom vi vet att allt till kvar av där vi för närvarande måste vara lägre än den värde som vi är närvarande på. Och allt till höger om där vi är måste vara större än det värde som Vi bläddrar i. 

Så vad är pseudo steg för binär sökning? Vi upprepar processen tills matris eller, som vi gå igenom, sub matriser, mindre bitar av den ursprungliga arrayen är av storlek 0. Beräkna mittpunkten av den aktuella underordnade uppsättningen. 

Om värdet du letar efter i denna del av gruppen, sluta. Du hittade det. Toppen. Annars, om målet är mindre än vad som finns i mitten, så om det värde vi letar för är lägre än vad vi ser, upprepa denna process igen, men ändra slutpunkten i stället av att vara den ursprungliga slutföra full uppsättning, vara precis till vänster var vi bara tittat. 

Vi visste att mitt var för högt, eller målet var mindre än i mitten, och så det måste föreligga, om den överhuvudtaget finns i arrayen, någonstans till vänster om mittpunkten. Och så vi får ställa in arrayen plats precis till vänster av mittpunkten som ny slutpunkt. Omvänt, om målet är större än vad som finns i mitten, Vi gör exakt samma process, men i stället vi ändra startpunkten att vara precis till höger om mittpunkten vi bara beräknas. Och sedan vi börja processen igen. 

Låt oss visualisera detta, OK? Så det händer mycket och här, men här är en samling av de 15 elementen. Och vi kommer att hålla reda av en mycket mer saker den här gången. Så i linjär sökning, var vi bara bry sig om ett mål. Men den här gången vill vi bryr sig om var är vi börjar se, där stannar vi ser, och vad är mittpunkten av den aktuella uppsättningen. Så här går vi med binär sökning. Vi är ganska mycket bra att gå, eller hur? Jag kommer bara att lägga ner nedan här en uppsättning index. Detta är i grunden precis vad elementet i matrisen vi pratar om. Med linjär sökning, vi vård, eftersom vi behöver veta hur många element vi iteration över, men vi egentligen inte bry sig om vad elementet vi bläddrar i. I binär sökning, gör vi. Och så de är bara där som en liten guide. 

Så vi kan börja, eller hur? Tja, inte riktigt. Kom ihåg vad jag sa om binär sökning? Vi kan inte göra det på ett osorterade array annars, vi inte garantera att den vissa element eller värden inte misstag bort när vi bara besluta att ignorera halv av arrayen. 

Så steg ett med binär sökning är att du måste ha en sorterade arrayen. Och du kan använda någon av sorteringen algoritmer vi har talat om för att få dig till den positionen. Så nu är vi i ett läge där vi kan utföra binär sökning. 

Så låt oss upprepa processen steg för steg och hålla koll på vad som händer när vi går. Så det första vi måste göra är att beräkna mittpunkten av den aktuella uppsättningen. Tja, ska vi säga att vi är först och allt efter värdet 19. Vi försöker hitta numret 19. Den första delen av detta matris är belägen på index noll, och den sista delen av detta array ligger på index 14. Och så vi kallar dem början och slut. 

Så vi beräknar mittpunkten av sätta 0 plus 14 dividerat med 2; ganska enkelt mittpunkt. Och vi kan säga att mittpunkten är nu 7. Så är 15 det vi letar efter? Nej det är det inte. Vi letar efter 19. Men vi vet att 19 är större än vad vi hittade i mitten. 

Så vad vi kan göra är ändra startpunkten vara precis till höger om den mittpunkt, och upprepa processen igen. Och när vi gör det, nu säger vi nya startpunkten är array plats 8. Vad vi har faktiskt gjort är ignoreras allt till vänster om 15. Vi har eliminerat hälften av problemet, och nu, i stället för att behöva söka över 15 element i vår samling, vi bara måste söka över 7. Så 8 är den nya startpunkten. 14 är fortfarande slutpunkten. 

Och nu går vi över detta igen. Vi beräknar den nya mittpunkten. 8 plus 14 är 22 dividerat med 2 är 11. Är detta vad vi letar efter? Nej det är det inte. Vi letar efter ett värde som är mindre än vad vi just hittat. Så vi kommer att upprepa processen igen. Vi kommer att ändra slutpunkten till vara precis till vänster om mittpunkten. Så den nya slutpunkten blir 10. Och nu, det är bara en del av arrayen vi måste gå igenom. Så har vi nu eliminerat 12 av de 15 elementen. Vi vet att om 19 existerar i arrayen, det måste finnas någonstans mellan elementet nummer 8 och elementnumret 10. 

Så vi beräkna den nya mittpunkten igen. 8 plus 10 är 18 dividerat med 2 är 9. Och i detta fall, titta, den Målet är i mitten. Vi hittade precis vad vi letar efter. Vi kan stoppa. Vi avklarad en binär sökning. Okej. Så vi vet denna algoritm fungerar om målet är någonstans inne i matrisen. Gör detta algoritm arbete om målet är inte i arrayen? Nåväl, låt oss börja den igen, och den här gången, låt oss titta för elementet 16, som visuellt kan vi se existerar inte någonstans i matrisen. 

Startpunkten är återigen 0. Slutpunkten är återigen 14. De är indexen för den första och sista element i den kompletta arrayen. Och vi kommer att gå igenom processen vi bara gick igenom igen, försöka hitta 16, trots att visuellt kan vi redan tala om att det inte kommer att vara där. Vi vill bara se till att denna algoritm kommer i själva verket fortfarande att fungera på något sätt och inte bara lämna oss fastnat i en oändlig loop. 

Så vad är steget först? Beräkna mittpunkten av den aktuella uppsättningen. Vad är mittpunkten av den aktuella uppsättningen? Tja, det är 7, eller hur? 14 plus 0 delat med 2 är 7. Är 15 det vi letar efter? Nej. Det är ganska nära, men vi letar för ett värde något större än så. 

Så vet vi att det kommer att ingenstans till vänster om 15. Målet är större än vad som finns i mittpunkten. Och så sätter vi den nya startpunkten till vara precis till höger om mitten. Mittpunkten är för närvarande 7, så låt oss säga den nya startpunkten är 8. Och vad vi har på ett effektivt sätt gjort igen ignoreras hela vänstra halv av arrayen. 

Nu, vi upprepa bearbeta en gång. Beräkna den nya mittpunkten. 8 plus 14 är 22 dividerat med 2 är 11. Är 23 det vi letar efter? Tyvärr inte. Vi letar efter ett värde som är mindre än 23. Och så i det här fallet, kommer vi att ändra slutpunkten vara bara till vänster om den aktuella mittpunkten. Den nuvarande mittpunkt är 11, och så vi får ställa in den nya slutpunkten för nästa gång vi åker genom denna process till 10. 

Återigen, vi går igenom processen igen. Beräkna mittpunkten. 8 plus 10 delat med två är 9. Är 19 det vi letar efter? Tyvärr inte. Vi letar fortfarande efter ett antal mindre än så. Så vi kommer att ändra slutpunkten den här gången vara precis till vänster om mittpunkten. Mittpunkten är för närvarande 9, så slutpunkten kommer att vara 8. Och nu är vi bara ute vid en enda elementgrupp. 

Vad är mittpunkten i denna samling? Tja, börjar det på 8, det slutar vid 8, är mittpunkten 8. Är det vad vi letar efter? Söker vi 17? Nej, vi letar efter 16. Så om den finns i arrayen, Det måste finnas någonstans till vänster om där vi är idag. Så vad ska vi göra? Tja, vi ställa in slutpunkten vara bara till vänster om den aktuella mittpunkten. Så vi kommer att ändra slutpunkten till 7. Ser du vad som just hände här, men? Slå upp här nu. 

Start är nu större än slutet. I själva verket de två ändarna av vår samling har passerat, och startpunkten är nu efter slutpunkten. Tja, gör det inte vettigt, eller hur? Så nu, vad vi kan säga är att vi har en sub uppsättning av storlek 0. Och när vi kommit till denna punkt, kan vi nu garantera att elementet 16 existerar inte i arrayen, eftersom startpunkten och slutpunkt har passerat. Och så är det inte det. Nu märker att detta är något annorlunda än startpunkten och slut punkt är densamma. Om vi ​​hade letat för 17, skulle det ha varit i arrayen, och startpunkten och slutpunkt den sista iterationen innan dessa punkter i kors, vi skulle ha funnit 17 där. Det är bara när de passerar att vi kan garantera att elementet inte existerar i arrayen. 

Så låt oss ta en mycket färre steg än linjär sökning. I värsta fall, hade vi att dela upp en lista med n element upprepade gånger i halv att hitta målet, antingen för att målelementet kommer att vara någonstans i den sista division, eller om den inte finns alls. Så i värsta fall måste vi dela upp array-- vet du? Logga av n gånger; vi måste skära problemet i halv ett visst antal gånger. Det antal gånger är log n. 

Vad är det bästa scenariot? Tja, första gången vi beräkna mittpunkten, finner vi vad vi letar efter. I alla tidigare exempel på binär sökning Vi har precis gått över, om vi hade letat efter elementet 15, vi skulle ha funnit det omedelbart. Det var i början. Det var mittpunkten av det första försöket vid en split av en division i binär sökning. 

Och så i värsta fall binär sökning körs i log n, som är väsentligt bättre än linjär sökning, i värsta fall. I bästa fall, binär sökning körs i omega 1. Så binär sökning är en mycket bättre än linjär sökning, men du måste ta itu med processen för sortering arrayen först innan du kan utnyttja kraften i binär sökning. 

Jag är Doug Lloyd. Detta är CS 50.