>> 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.