[Speel van musiek] 

DOUG LLOYD: Alle reg. So binêre soek is 'n algoritme wat ons kan gebruik om 'n element te vind binne 'n skikking. Anders lineêre soek, dit vereis 'n spesiale voorwaarde vooraf ontmoet het, maar dit is soveel meer doeltreffend as daardie toestand is, in werklikheid, ontmoet het. 

So, wat is die idee hier? dit is Verdeel en oorwin. Ons wil die grootte van te verminder die soektog gebied met 'n halwe elke keer ten einde 'n teiken nommer te vind. Dit is waar dat voorwaarde kom in die spel, al is. Ons kan net die krag van die hefboom uitskakeling helfte van die elemente sonder om eers na hulle as die skikking gesorteer. 

As dit is 'n volledige meng, Ons kan nie net uit die hand weggooi helfte van die elemente, want ons weet nie wat ons wegdoen. Maar as die skikking gesorteer, kan ons dit doen, omdat ons weet dat alles aan die links van waar ons tans is moet laer as die wees waarde wat ons is tans op. En alles aan die reg van die plek waar ons is moet groter as die waarde ons is tans op soek na. 

So, wat is die pseudokode stappe vir binêre soek? Ons herhaal die proses totdat die array of, as ons voortgaan deur, sub skikkings, kleiner stukke die oorspronklike skikking, is die grootte 0. Bereken die middelpunt van die huidige sub skikking. 

Indien die waarde wat jy soek is in daardie element van die skikking, stop. Jy het dit gevind. Dit is 'n groot. Andersins, as die teiken is minder as wat is aan die middel, so as die waarde wat ons soek vir laer is as wat ons sien, herhaal hierdie proses nie, maar verander die eindpunt, in plaas om die oorspronklike voltooi volle reeks, wees net aan die linkerkant van waar ons net gekyk. 

Ons het geweet dat die middel te hoog was, of die teiken was minder as die middel, en so moet dit bestaan ​​nie, as dit bestaan ​​op alle in die skikking, iewers aan die linkerkant van die middelpunt. En so sal ons die skikking stel plek net aan die linkerkant van die middelpunt as die nuwe eindpunt. Omgekeerd, indien die teiken is groter as wat is aan die middel, ons presies dieselfde te doen proses, maar in plaas daarvan verander die begin punt om te wees net aan die regterkant van die middelpunt ons het net bereken. En dan, weer begin ons die proses. 

Kom ons visualiseer dit OK? So is daar 'n baie gaan en hier, maar hier is 'n verskeidenheid van die 15 elemente. En ons gaan word die dop van 'n baie meer dinge hierdie tyd. So in lineêre soek, was ons net omgee oor 'n teiken. Maar hierdie keer wil ons omgee waar is ons begin om te kyk waar ons stop soek, en wat is die middelpunt van die huidige skikking. So hier gaan ons met binêre soek. Ons is pretty much goed om te gaan, reg? Ek gaan net om neer te sit hieronder hier 'n stel van indekse. Dit is basies net wat element van die skikking wat ons praat. Met lineêre soek, ons omgee, omdat ons nodig om te weet hoeveel elemente ons iterating oor, maar ons weet nie eintlik omgee wat element ons is tans op soek na. In binêre soek, ons doen. En so dit is net daar as 'n bietjie gids. 

So kan ons begin, reg? Wel, nie heeltemal nie. Onthou wat ek gesê het oor binêre soek? Ons kan dit nie doen nie op 'n ongesorteerde array of anders, ons is nie waarborg dat die sekere elemente of waardes is nie per ongeluk weggegooi toe ons net besluit om die helfte van die skikking te ignoreer. 

So stap een met binêre soek is moet jy 'n verskeidenheid gesorteer het. En jy kan enige van die sortering gebruik algoritmes ons het gepraat oor om jou te kry om daardie posisie. So nou, ons is in 'n posisie waar kan ons binêre soek uit te voer. 

So laat herhaal die proses stap vir stap en hou spoor van wat gebeur as ons gaan. So die eerste moet ons doen, is bereken die middelpunt van die huidige skikking. Wel, sal ons sê ons is, in die eerste al, op soek na die waarde 19. Ons probeer om die nommer 19 vind. Die eerste element van hierdie verskeidenheid is geleë op indeks nul, en die laaste element van hierdie verskeidenheid is geleë op 14-indeks. En so sal ons daardie begin en einde te bel. 

Sodat ons bereken die middelpunt deur toevoeging van 0 plus 14 gedeel deur 2; redelik eenvoudig middelpunt. En ons kan sê dat die middelpunt is nou 7. So is 15 wat ons soek? Nee dit is nie. Ons is op soek na 19. Maar ons weet dat 19 groter is as wat ons gevind op die middel. 

So, wat ons kan doen is verander die begin punt wees net aan die regterkant van die middelpunt, en weer herhaal die proses. En wanneer ons dit doen, nou sê ons die nuwe begin punt is verskeidenheid ligging 8. Wat ons gedoen het, is effektief geïgnoreer alles aan die linkerkant van 15. Ons het uitgeskakel helfte van die probleem, en nou, in plaas van om te soek meer as 15 elemente in ons verskeidenheid, ons het net om te soek oor 7. So 8 is die nuwe begin punt. 14 is nog steeds die eindpunt. 

En nou, ons gaan oor dit weer. Ons bereken die nuwe middelpunt. 8 plus 14 is 22, gedeel deur 2 is 11. Is dit wat ons soek? Nee dit is nie. Ons is op soek na 'n waarde wat minder as wat ons nou net gevind. So ons gaan herhaal die proses weer. Ons gaan na die eindpunt te verander net aan die linkerkant van die middelpunt. So het die nuwe eindpunt word 10. En nou, dit is die enigste deel van die skikking het ons om te sorteer. So het ons nou uitgeskakel 12 van die 15 elemente. Ons weet dat as 19 bestaan ​​in die skikking, dit moet tussen element iewers bestaan nommer 8 en element nommer 10. 

So het die nuwe middelpunt weer bereken ons. 8 plus 10 is 18, gedeel deur 2 is 9. En in hierdie geval, kyk, die teiken is op die middel. Ons het gevind dat presies wat ons soek. Ons kan stop. Ons suksesvol voltooi 'n binêre soek. Alles reg. So ons weet hierdie algoritme werk as die teiken is iewers binnekant van die skikking. Doen hierdie algoritme werk as die teiken is nie in die skikking? Wel, kom ons begin dit weer, en hierdie keer, Kom ons kyk vir die element 16, wat visueel kan ons sien nêrens bestaan ​​in die skikking. 

Die begin punt is weer 0. Die eindpunt is weer 14. Dit is die indekse van die eerste en laaste elemente van die volledige skikking. En ons gaan deur die proses het ons net weer het deur, probeer om uit te vind 16, selfs al visueel, kan ons reeds sê dat dit nie gaan om daar te wees. Ons wil net om seker te maak hierdie algoritme maak sal, in werklikheid, nog steeds werk in een of ander manier en nie net laat ons vas in 'n oneindige lus. 

So, wat is die stap eerste? Bereken die middelpunt van die huidige skikking. Wat is die middelpunt van die huidige reeks? Wel, dit is 7, reg? 14 plus 0 gedeel deur 2 is 7. 15 wat ons soek? Geen. Dit is redelik naby, maar ons is op soek vir 'n waarde effens groter as dit. 

So weet ons dat dit gaan nêrens aan die linkerkant van 15. Die teiken is groter as Wat is in die middelpunt. En so het ons het die nuwe begin punt om net aan die regterkant van die middel. Die middelpunt is tans 7, so Kom ons sê die nuwe begin punt is 8. En wat ons effektief het weer gedoen word geïgnoreer die hele linker helfte van die skikking. 

Nou, ons herhaal die verwerk een keer. Bereken die nuwe middelpunt. 8 plus 14 is 22, gedeel deur 2 is 11. Is 23 wat ons soek? Ongelukkig nie. Ons is op soek na 'n waarde dit is minder as 23. En so in hierdie geval, ons gaan tot aan die einde punt te verander na net aan die linkerkant van die huidige middelpunt. Die huidige middelpunt is 11, en so sal ons die nuwe eindpunt stel vir die volgende keer gaan ons deur hierdie proses tot 10. 

Weereens, ons gaan deur die proses weer. Bereken die middelpunt. 8 plus 10 gedeel deur 2 is 9. Is 19 wat ons soek? Ongelukkig nie. Ons is nog op soek na 'n aantal minder as dit. So sal ons die eindpunt hierdie tyd verander wees net aan die linkerkant van die middelpunt. Die middelpunt is tans 9, so die eindpunt sal wees 8. En nou, ons soek net op 'n enkele element skikking. 

Wat is die middelpunt van hierdie verskeidenheid? Wel, dit begin by 8, is dit eindig by 8, die middelpunt is 8. Is dit wat ons soek? Is ons op soek na 17? Nee, ons is op soek na 16. So as dit bestaan ​​in die skikking, dit moet êrens bestaan aan die linkerkant van waar ons tans is. So, wat gaan ons doen? Wel, ons sal die einde punt stel om net aan die linkerkant van die huidige middelpunt. So sal ons die eindpunt te verander na 7. Sien jy wat net hier gebeur, al is? Kyk nou hier. 

Begin nou groter as die einde. Effektief, die twee ente van ons verskeidenheid gekruis het, en die begin punt is nou na die eindpunt. Wel, dit doen nie maak geen sin, reg? So nou, wat ons kan sê, is ons 'n sub verskeidenheid van grootte 0. En sodra ons gekry om hierdie punt, kan ons nou waarborg dat element 16 bestaan ​​nie in die skikking, omdat die begin punt en eindpunt gekruis het. En so is dit nie daar nie. Nou, sien dat hierdie is 'n bietjie anders as die begin en die einde punt punt is dieselfde. As ons was op soek vir 17, sou dit in die skikking, en die begin punt is en eindpunt van die laaste iterasie voordat die punte oorgesteek, Ons sou daar gevind 17. Dit is net wanneer hulle oor wat ons kan waarborg dat die element nie bestaan ​​in die skikking. 

So laat ons 'n baie minder stappe as lineêre soek. In die ergste geval scenario, het ons te verdeel 'n lys van n elemente herhaaldelik in die helfte om die teiken te vind, óf omdat die teiken element sal in die laaste iewers afdeling, of dit nie bestaan ​​nie by almal. So in die ergste geval, ons het om te verdeel die array-- weet jy? Teken van n keer; ons het om die probleem op te sny in die helfte van 'n sekere aantal kere. Dat die getal kere is log n. 

Wat is die beste scenario? Wel, die eerste keer dat ons bereken die middelpunt, vind ons wat ons soek. In al die vorige voorbeelde van binêre soek Ons het net gegaan oor, as ons het is op soek na die element 15, ons dat onmiddellik sou gevind het. Dit was aan die begin. Dit was die middelpunt van die eerste poging om 'n skeuring van 'n afdeling in binêre soek. 

En so in die ergste geval, binêre soek loop in log N, wat aansienlik beter as lineêre soek, in die ergste geval. In die beste geval, binêre soek lopies in omega van 1. So binêre soek is 'n baie beter as lineêre soek, maar jy het om te gaan met die proses van sorteer jou array eerste voordat jy kan die invloed van die krag van binêre soek. 

Ek is Doug Lloyd. Dit is CS 50.