ROB BOWDEN: Hi, ek is Rob. Hoe kan ons in diens 'n binêre soek? Kom ons vind uit. So, daarop te let dat dit soek gaan ons rekursief implementeer. Jy kan ook implementeer binêre soek iteratief, so as jy dit gedoen het, dit is heeltemal fyn. 

Nou eers, laat ons onthou wat die parameters te soek, is bedoel om te wees. Hier sien ons int waarde, wat veronderstel om die waarde van die gebruiker is om te wees soek. Ons sien die int waardes skikking, wat is die skikking in wat ons is soek na waarde. En ons sien int n, wat Die lengte van ons verskeidenheid. 

Nou, in die eerste ding wat eerste. Ons gaan om te sien of n gelyk aan 0, in welke geval ons terugkeer onwaar. Dit is net te sê as ons 'n leë skikking, waarde is duidelik nie in 'n leë skikking, sodat ons kan terugkeer onwaar. 

Nou, ons wil eintlik die binêre te doen Soek deel van binêre soek. So, ons wil die middel te vind element van hierdie reeks. Hier sê ons middel gelyk aan n verdeelde deur 2, sedert die middel element is gaan die lengte van te wees Ons verskeidenheid gedeel deur 2. Nou gaan ons kyk of die Midde-element is gelyk aan die waarde wat ons is soek. So as waardes middel gelyk aan waarde, het ons kan terugkeer waar nie, aangesien ons het die waarde in ons verskeidenheid. 

Maar as dit nie waar was nie, nou Ons moet die rekursiewe te doen stap van binêre soek. Ons moet óf om te soek na die links van die skikking of die middel van die skikking. So hier is, sê ons as waardes by die middel is minder as waarde, wat beteken dat waarde groter as die middel was van die skikking. So waarde moet aan die regterkant van die wees element wat ons nou net gekyk. 

So hier gaan ons soek rekursief. En ons sal sien wat ons verby om dit in 'n tweede. Maar ons gaan soek na die regs van die middel element. En in die ander geval is, wat beteken dat waarde was minder as die helfte van die skikking, en so gaan ons om te soek na die linkerkant. Nou, is die links gaan wees 'n bietjie makliker om te kyk na. So, hier sien ons dat ons rekursief roep soek waar die eerste argument is, weer, die waarde ons is op soek verby. Die tweede argument gaan wees om die skikking wat ons is op soek verby. En die laaste element is nou middel. Onthou die laaste parameter is ons int n, so dit is die lengte van ons verskeidenheid. 

In die rekursiewe oproep om te soek, ons is nou te sê dat die lengte van die skikking is middel. So, as ons verskeidenheid was van grootte 20 en ons deursoek indeks 10, sedert die middel is 20 gedeel deur 2, wat beteken dat ons verby 10 as die nuwe lengte van ons verskeidenheid. Onthou dat wanneer jy 'n verskeidenheid 'n lengte van 10, wat beteken dat die geldige elemente is in indekse 0 tot 9. So dit is presies wat ons wil spesifiseer ons opgedateer verskeidenheid - die linker verskeidenheid van die middel element. 

So, op soek na die regte is 'n bietjie meer moeilik. Nou eers, laat ons kyk na die lengte van die skikking aan die regterkant van die Midde-element. So, as ons verskeidenheid was van grootte n, dan is die nuwe skikking sal van grootte n minus wees middel minus 1. So, laat ons dink aan n minus middel. 

Weereens, as die skikking was van grootte 20 en ons deur 2 die middel te kry, sodat die middel is 10, dan n minus middel gaan gee ons 10, so 10 elemente aan die regterkant van die middel. Maar ons het ook die minus 1, want ons wil nie sluit in die middel self. So n minus middel minus 1 gee ons die totale aantal elemente aan die regterkant van die middel-indeks in die skikking. 

Nou hier, onthou dat die middel parameter is die waardes skikking. So hier is ons verby 'n opgedateer waardes skikking. Hierdie waardes plus middel plus 1 is eintlik sê rekursief roep Soek, verby in 'n nuwe skikking, waar dat die nuwe reeks begin in die middel plus een van ons oorspronklike waardes skikking. 

'N alternatiewe sintaksis vir wat, nou dat jy begin wysers te sien, is ampersand waardes middel plus 1. So, gryp die adres van die middel plus een element van waardes. 

Nou, as jy nie gemaklik wysiging van 'n skikking soos wat jy kon ook geïmplementeer hierdie gebruik 'n rekursiewe funksie helper, waar dat helper funksie neem meer argumente. So in plaas van om net die waarde, die skikking, en die grootte van die skikking, die helper funksie meer kan neem argumente, insluitend die laer indeks wat jy sal omgee in die skikking en die boonste indeks dat jy omgee oor die skikking. 

En so hou van beide die laer indeks en die boonste indeks, wat jy doen nie nodig om ooit te verander oorspronklike waardes skikking. Jy kan net voortgaan om te Gebruik die waardes skikking. Maar hier, sien ons nie 'n hulp nodig het nie funksioneer solank as wat ons is bereid is om die oorspronklike te verander waardes skikking. Ons is bereid om te slaag in 'n updated waardes. 

Nou kan ons nie binêre soek oor 'n skikking wat ongesorteerde. So, laat ons kry dit uitgesorteer. Nou, sien dat die soort is afgelope twee parameters int waardes, wat is die skikking wat ons sorteer, en int n, wat is die lengte van die skikking wat ons sorteer. So, hier is ons wil implementeer 'n sorteeralgoritme wat o N vierkantig. Jy kan borrel soort, seleksie kies soort, of voeg soort, of 'n ander soort ons het nie gesien in die klas. Maar hier, ons gaan gebruik seleksie soort. 

So, gaan ons Itereer oor die hele skikking. Wel, hier sien ons dat ons iterating van 0 tot n minus 1. Hoekom nie al die pad tot n? Wel, die eerste as ons het reeds uitgesorteer n minus 1 elemente, dan is die heel laaste element wat moet reeds op die regte plek, so sorteer oor die hele skikking. 

Nou, onthou hoe seleksie soort werk. Ons gaan om te gaan oor die hele skikking soek na die minimum waarde in die skikking en stok wat aan die begin. Daarna het ons gaan om te gaan oor die hele skikking weer op soek na die tweede kleinste element, en die stok wat in die tweede posisie in die skikking, en so aan. So, dit is wat dit is om te doen. 

Hier, ons sien dat ons die opstel van die huidige minimum waarde tot die i-de-indeks. So op die eerste iterasie, ons gaan oorweeg die minimum waarde te wees die begin van ons verskeidenheid. Dan gaan ons Itereer oor die res van die skikking, monitor om te sien of daar enige elemente kleiner as die een wat ons tans oorweging van die minimum te beperk. 

So hier, waardes j plus een - dit is minder as wat ons tans oorweging van die minimum te beperk. Dan gaan ons te werk wat ons dink is die minimum te indeks j plus 1. So, doen wat oor die hele skikking, en nadat dit vir lus, minimum moet die minimum element van die i-de posisie in die skikking. 

Sodra ons het, kan ons ruil die minimum waarde in die i-de posisie in die skikking. So dit is net 'n standaard ruil. Ons slaan in 'n tydelike waarde - die i-de waarde van die skikking - sit in die i-de waarde in die skikking minimum waarde dat daar hoort, en dan slaan terug in waar die huidige minimum waarde wat gebruik word om die wees i-de waarde van die skikking, so dat ons nie verloor nie. 

So, wat steeds op die volgende iterasie. Ons sal begin soek na die tweede minimum waarde en voeg wat in die tweede posisie. Op die derde iterasie, sal ons kyk vir die derde minimum waarde en voeg wat in die derde posisie, en so totdat ons 'n gesorteerde skikking. My naam is Rob, en hierdie was seleksie soort.