>> [Muziek]
>> DOUG LLOYD: Oké.
Dus binary search is een algoritme we kunnen gebruiken
een element vindt in een matrix.
Unlike lineair zoeken, vereist een speciale voorwaarden vooraf worden voldaan,
maar het is zo veel efficiënter als deze voorwaarde is in feite ontmoet.
>> Dus wat is het idee hier?
het is verdeel en heers.
We willen de grootte van de te verminderen het zoekgebied met de helft elke keer
teneinde een target nummer.
Dit is waar dat de toestand in het spel komt, dat wel.
We kunnen alleen maar de kracht van het hefboomeffect waardoor de helft van de elementen
zonder zelfs maar te kijken naar ze als de array wordt gesorteerd.
>> Als het een complete mix, We kunnen niet zomaar uit de hand
gooi de helft van de elementen, omdat we weten niet wat we weggooien.
Maar als de matrix wordt gesorteerd, kunnen we dat doen, omdat we
weet dat alles aan de links van waar we nu zijn
moet lager zijn dan de waar we momenteel.
En alles aan de rechts van waar we zijn
groter zijn dan de waarde we bent momenteel.
>> Dus wat is het pseudocode stappen voor binaire zoeken?
We herhalen dit proces tot de array of, als we verder door,
sub arrays kleinere stukken de oorspronkelijke array, is de grootte 0.
Bereken het middelpunt van de huidige sub-array.
>> Als de waarde die u zoekt naar in dat element van de array stoppen.
U vond het.
Dat is geweldig.
Anders, als het doel minder dan wat er in het midden,
dus als de waarde die we zoeken voor het lager is dan wat we zien,
herhaal dit proces, maar wijzigt het eindpunt, in plaats
dat het de originele voltooien volledige reeks,
zijn net aan de linkerkant waar we keek.
>> We wisten dat het midden te hoog was, of het doelwit was lager dan het midden,
en dus moet bestaan, indien al bestaat in de array,
iets links van het midden.
En dus zullen we de array ingesteld locatie net aan de linkerkant
van het middelpunt als het nieuwe eindpunt.
Omgekeerd, als het doel groter dan wat er in het midden,
we precies hetzelfde doen proces, maar we
wijzigt het beginpunt te zijn net rechts van het middelpunt
we net berekend.
En dan opnieuw beginnen we het proces.
>> Laten we dit visualiseren, OK?
Dus er is veel te doen en hier, maar hier is een array van 15 elementen.
En we gaan worden bijhouden van veel meer dingen deze keer.
Dus in lineair zoeken, waren we gewoon zorgen te maken over een doel.
Maar deze keer willen we schelen waar zijn we
beginnen te kijken, waar de stoppen we kijken,
en wat is het middelpunt van de huidige rij.
Dus hier gaan we met binaire zoeken.
We zijn vrij veel goed om te gaan, toch?
Ik ga gewoon neer te zetten Hieronder hier een set indices.
Dit is eigenlijk precies wat element van de array we het over hebben.
Met lineair zoeken wij zorg, aangezien we
moeten weten hoeveel elementen we itereren over,
maar we eigenlijk niet schelen wat element we bent momenteel.
In binaire zoeken, we doen.
En dus die zijn daar als een kleine gids.
>> Dus we kunnen beginnen, toch?
Nou, niet helemaal.
Vergeet niet wat ik zei ongeveer binaire zoeken?
We kunnen het niet op ongesorteerde array of anders,
wij niet garanderen dat de bepaalde elementen of waarden niet
ongeluk weggegooid toen we net
besluiten helft van de matrix negeren.
>> Dus stap één met binaire zoeken is dat je moet een gesorteerde array.
En je kunt een van de sortering gebruiken algoritmes we hebben gesproken over
om u naar die positie.
Dus nu zijn we in een positie waar kunnen we binaire zoeken.
>> Dus laten we het proces herhalen stap voor stap en houden
spoor van wat er gebeurt als we verder gaan.
Dus de eerste moeten we doen is te berekenen het middelpunt van de huidige rij.
Nou, zullen we zeggen dat we in de eerste plaats alle, op zoek naar de waarde 19.
We proberen om het nummer 19 te vinden.
Het eerste element van deze matrix zich op index nul,
en het laatste element van deze matrix zich op index 14.
En dus zullen we die begin en einde noemen.
>> Dus we berekenen het middelpunt van het toevoegen van 0 plus 14 gedeeld door 2;
vrij eenvoudig middelpunt.
En we kunnen zeggen dat het middelpunt is nu 7.
Zo is 15 wat we zoeken?
Nee, dat is het niet.
We zijn op zoek naar 19.
Maar we weten dat 19 groter dan wat we in het midden.
>> Dus wat we kunnen doen is wijzigt het beginpunt
om net rechts van het middelpunt, en herhaal het proces.
En als we dat doen, nu zeggen we het nieuwe start punt is scala locatie 8.
Wat we hebben gedaan is effectief genegeerd alle links van 15.
We hebben geëlimineerd de helft van het probleem, en nu,
in plaats van te zoeken meer dan 15 elementen in onze array,
we hebben alleen te zoeken meer dan 7.
Dus 8 is het nieuwe startpunt.
14 blijft het eindpunt.
>> En nu gaan we dan dit weer.
We berekenen de nieuwe middelpunt.
8 plus 14 is 22, gedeeld door 2 is 11.
Is dit wat we zoeken?
Nee, dat is het niet.
We zijn op zoek naar een waarde die is minder dan wat we vonden.
Dus we gaan om te herhalen het proces opnieuw.
We gaan naar het eindpunt te veranderen net links van het midden.
Zodat het nieuwe eindpunt wordt 10.
En nu, dat is het enige deel van de serie hebben we te sorteren.
Dus hebben we nu geëlimineerd 12 van de 15 elementen.
We weten dat als 19 bestaat in de array, zij
moet tussen element ergens bestaan nummer 8 en element nummer 10.
>> Dus de nieuwe middelpunt opnieuw berekenen we.
8 plus 10 is 18, gedeeld door 2 is 9.
En in dit geval, kijk, de doelstelling is in het midden.
Vonden we precies wat we zoeken.
We kunnen stoppen.
We succesvol afgerond een binair zoeken.
Prima.
Dus we weten dit algoritme werkt als het doel is
ergens in de array.
Doet dit algoritme werk als het doel niet in de array?
Nou, laten we starten weer en ditmaal,
laten we eens kijken naar het element 16, die visueel kunnen we zien
bestaat nergens in de array.
>> Het startpunt is weer 0.
Het eindpunt weer 14.
Dat zijn de indices van de eerste en laatste elementen van de volledige array.
En we gaan door middel van het proces dat we net weer ging door, proberen te vinden 16,
hoewel visueel, kunnen we nu al vertellen dat het niet gaat om daar te zijn.
We willen gewoon zeker van dat dit algoritme zal in feite nog steeds werken op een bepaalde manier
en niet alleen laat ons geplakt in een oneindige lus.
>> Dus wat is de eerste stap?
Bereken het middelpunt van de huidige rij.
Wat is het middelpunt van de huidige reeks?
Nou, het is 7, toch?
14 plus 0 gedeeld door 2 is 7.
Is 15 wat we zoeken?
Nee.
Het is vrij dicht, maar we zijn op zoek voor een waarde iets groter dan dat.
>> Dus we weten dat het gaat om zijn nergens links van 15.
Het doel is groter dan wat er in het midden.
En dus zetten we de nieuwe start punt net rechts van het midden.
Het middelpunt is momenteel 7, zodat laten we zeggen dat het nieuwe startpunt is 8.
En wat we effectief hebt weer gedaan wordt genegeerd
het gehele linkerhelft van de array.
>> Nu, we herhalen verwerken nog een keer.
Bereken het nieuwe middelpunt.
8 plus 14 is 22, gedeeld door 2 is 11.
23 is wat we zoeken?
Helaas niet.
We zijn op zoek naar een waarde die kleiner is dan 23.
En dus in dit geval, we gaan het eindpunt veranderen gewoon
links van het huidige middelpunt.
De huidige middelpunt is 11, en dus zullen we de nieuwe eindpunt in te stellen
voor de volgende keer dat we gaan door dit proces te 10.
>> Nogmaals, we gaan door het proces opnieuw.
Bereken het middelpunt.
8 plus 10 gedeeld door 2 is 9.
19 is wat we zoeken?
Helaas niet.
We zijn nog op zoek naar een getal kleiner dan dat.
Dus we het eindpunt van deze tijd te veranderen zijn net links van het midden.
Het middelpunt is momenteel 9, dus het eindpunt zal zijn 8.
En nu, we zijn gewoon op zoek in een enkel element array.
>> Wat is het middelpunt van deze serie?
Nou, het begint op 8, dat 8 eindigt bij het middelpunt is 8.
Is dat wat we zoeken?
Zijn wij op zoek naar 17?
Nee, we zijn op zoek naar 16.
Dus indien aanwezig in de matrix, moet ergens aanwezig
aan de linkerkant van waar we nu zijn.
Dus wat gaan we doen?
Nou, we zullen het eindpunt in te stellen om alleen te zijn links van het huidige middelpunt.
Dus we het eindpunt te veranderen tot 7.
Zie je wat er zojuist is hier gebeurd, hoewel?
Kijk hier nu.
>> Start is nu groter dan eind.
Effectief, de beide einden van ons aanbod hebben gekruist,
en het startpunt is nu na het eindpunt.
Nou, dat doet niet geen zin, toch?
Dus nu, wat we kunnen zeggen is dat we een sub-matrix van grootte 0.
En zodra we gekregen om dit punt, kunnen we nu
waarborgen dat element 16 bestaat niet in de array,
omdat het beginpunt en eindpunt hebben gekruist.
En dus is het er niet.
Nu, merken dat dit is iets anders dan het begin en eindpunt
punt is hetzelfde.
Als we waren op zoek 17, zou het
in de array, en het startpunt geweest en eindpunt van die laatste iteratie
voor die punten gekruist, we zouden er hebben 17.
Het is pas wanneer ze steken dat we kunnen waarborgen dat het element niet
bestaan ​​in de array.
>> Dus laten we eens een stuk minder stappen dan lineair zoeken.
In het ergste geval, hadden we op te splitsen een lijst van n elementen
herhaaldelijk helft het doel te vinden, hetzij omdat het doelelement
zal in de laatste ergens divisie of het niet bestaat helemaal niet.
Dus in het ergste geval, we splitsen de array-- weet je dat?
Log n keer; we het probleem moeten snijden
in halve bepaald aantal keren.
Dat aantal keren is log n.
>> Wat is de beste case scenario?
Nou, de eerste keer dat we berekent het middelpunt,
we vinden wat we zoeken.
In alle voorgaande voorbeelden op binaire zoekopdracht
we hebben gewoon weg over, als we hadden op zoek naar het element 15,
we die onmiddellijk zou hebben gevonden.
Dat was in het begin.
Dat was het middelpunt van de eerste poging tot een split
van een divisie in binaire zoeken.
>> En zo in het ergste geval, binary search loopt
log n, die aanzienlijk beter dan lineair zoeken, in het ergste geval.
In het beste geval binary search draait in omega van 1.
Dus binaire zoektocht is een veel beter dan lineaire zoeken,
maar heb je te maken met het proces van de sorteren van de array eerst voordat je kunt
maken gebruik van de kracht van de binaire zoekopdracht.
>> Ik ben Doug Lloyd.
Dit is CS 50.