>> ROB BOWDEN: Sveiki, es esmu Rob.
Kā mēs izmantot bināro meklēšanu?
Let 's uzzināt.
Tātad, ņemiet vērā, ka šo meklējumu mēs ejam īstenot rekursīvi.
Jūs varētu arī īstenot bināro meklēšanu iteratīvi, tādēļ, ja jūs, ka,
tas ir pilnīgi naudas sodu.
>> Tagad pirmo reizi, atcerēsimies, kāda parametrus, lai meklētu, ir domāts, lai būtu.
Šeit mēs redzam, int vērtību, kas ir vajadzētu būt vērtība ir lietotājs
meklē.
Mēs redzam, ka int vērtības masīvs, kas ir masīvs, kurā mēs esam
meklējot vērtības.
Un mēs redzam, int n, kas ir garums mūsu masīvs.
>> Tagad, pirmā lieta, pirmkārt.
Mēs pārbaudām, vai n ir vienāds ar 0, jo un tādā gadījumā mēs atgriežamies nepatiesa.
Tas ir tikai saprotams, ja mums ir tukšs masīvs, vērtība ir acīmredzami nav
tukšs masīvs, lai mēs varētu atgriezties viltus.
>> Tagad mēs patiešām vēlamies darīt bināro meklēšana daļa bināro meklēšanu.
Tātad, mēs vēlamies, lai atrastu vidū Šī masīva elements.
Lūk, mēs sakām vidū ir vienāds ar n dalīts ar 2, jo vidus elements ir
būs garums Mūsu masīvs dalīts ar 2.
Tagad mēs esam gatavojas pārbaudīt, lai redzētu, vai vidū elements ir vienāds ar vērtību, mēs esat
meklē.
Tātad, ja vērtības vidū ir vienāda vērtība, mēs var atgriezties taisnība, jo mēs atradām
vērtība mūsu masīvā.
>> Bet, ja tas nav taisnība, tagad mums ir jādara rekursīvs
solis bināro meklēšanu.
Mums ir jāmeklē vai nu kreisi no masīva vai
vidū masīva.
Tātad šeit, mēs sakām, ja vērtības, kas pa vidu ir mazāk nekā vērtība, tas nozīmē, ka šo vērtību
ir lielāks nekā vidu masīva.
Tā vērtība ir jābūt tiesībām elements, ka mēs vienkārši paskatījās.
>> Tātad šeit mēs gatavojamies meklēt rekursīvi.
Un mēs apskatīt to, ko mēs esam iet uz šo sekundē.
Bet mēs ejam meklēt, lai tiesības vidū elementa.
Un otrā gadījumā tas nozīmē, ka vērtība ir mazāka nekā vidū
masīvs, un tā mēs ejam meklēt pa kreisi.
Tagad, pa kreisi būs mazliet vieglāk apskatīt.
Tātad, mēs redzam šeit, ka mēs esam rekursīvi aicinot meklēt, kur pirmais
arguments ir, atkal, vērtība mēs meklējam vairāk.
Otrais arguments būs masīvs, ka mēs meklēt vairāk.
Un pēdējais elements tagad vidū.
Atcerieties pēdējais parametrs ir mūsu int n, tā ka ir garums mūsu masīvs.
>> Ar rekursīvas zvanu, lai meklētu, mēs esam tagad saka, ka garums
masīvs ir vidū.
Tātad, ja mūsu masīvs bija lieluma 20 un mēs meklēja pie indeksu 10, jo pa vidu ir
20 dalīts ar 2, tas nozīmē, ka mēs esam iet 10, jo jaunā
garums mūsu masīvs.
Atcerieties, ka, ja jums ir masīvs garuma 10, tas nozīmē, ka ir spēkā
elementi ir indeksiem 0 līdz 9.
Tātad, tas ir tieši tas, ko mēs vēlamies, lai precizēt mūsu atjaunināto masīvs - kreiso
masīvs no vidējā elementa.
>> Tātad, meklē labi ir mazliet grūtāk.
Tagad pirmo reizi, pieņemsim apsvērt garumu masīva uz tiesībām
vidū elements.
Tātad, ja mūsu masīvs bija lieluma n, tad Jaunais masīvs būs lielums n mīnusu
vidējā mīnus 1.
Tātad, pieņemsim domāt n mīnus vidū.
>> Atkal, ja masīvs bija lieluma 20 un mēs sadalīt pa 2, lai iegūtu vidū,
tā vidū ir 10, tad n mīnus vidū gatavojas sniegt mums 10, tāpēc 10
elementi pa labi pa vidu.
Bet mums arī ir šī mīnus 1, jo mēs nevēlamies
ietver vidū pati.
Tātad n mīnus vidējā mīnus 1 dod mums kopskaits elementu labās
no vidējā indeksa masīvā.
>> Tagad šeit, atcerieties, ka vidējā parametrs ir vērtību masīvs.
Tātad šeit mēs iet papildināta vērtības masīvs.
Šis vērtības plus vidējā plus 1 ir patiesībā sakot rekursīvi zvaniet
meklēšana, kas iet jaunā masīvs, kur ka jaunā masīva sākas vidū
plus viens no mūsu sākotnējās vērtības bloku.
>> Aizstājējs sintakse, ka tagad, Jūs esat sācis redzēt norādes, ir
Ampersand vērtību vidū, kā arī 1.
Tātad, greifers adresi vidū plus viens elements no vērtībām.
>> Tagad, ja jūs neesat apmierināti pārveidojot masīvu, piemēram, ka jūs
arī varētu būt īstenoti to, izmantojot rekursīvs palīgs funkcija, kur
ka palīgs funkcija tiek vairāk argumenti.
Tā vietā, lai veiktu tikai vērtību, masīvs, un lielumu masīva,
palīgs funkcijas varētu uzņemties vairāk argumentus, tajā skaitā zemāko indeksu
ka jūs varētu rūpēties par masīvā un augšējo indeksu, ka jūs aprūpi
par masīvu.
>> Un tā sekotu gan zemākas indekss un augšējo indeksu, jums nav
nepieciešams, lai kādreiz mainīt sākotnējās vērtības masīvs.
Jūs varat turpināt izmantot vērtības masīvu.
Bet šeit, paziņojums mums nav vajadzīgs palīgs darboties tik ilgi, kamēr mēs esam
vēlas mainīt oriģinālu vērtības masīvs.
Mēs esam gatavi pāriet modernizēta vērtības.
>> Tagad mēs nevaram bināro meklēšanu pār masīvs, kas ir nešķirotas.
Tātad, pieņemsim iegūt šo sakārtoti.
Tagad, ievērosiet, ka veids ir pēdējo divu parametri int vērtības, kas ir
masīvs, ka mēs esam šķirošana, un int n, kas ir garums masīva ka
mēs esam šķirošana.
Tātad, šeit mēs vēlamies īstenot šķirošanas algoritms
kas ir o n brusas.
Jūs varētu izvēlēties burbuļa kārtošanas, atlases kārtot vai ievietošanas kārtot, vai
kāda cita veida mums nav redzējuši klasē.
Bet šeit, mēs ejam, lai izmantot atlases veida.
>> Tātad, mēs esam gatavojas atkārtot visam blokam.
Nu, šeit mēs redzam, ka mēs esam atkārtojot mīnus no 0 līdz n 1.
Kāpēc ne visu ceļu līdz pat n?
Nu, ja mēs jau esam sakārtoti pirmais n mīnus 1 elementi, tad
Ļoti pēdējais elements, kas jau jābūt pareizajā vietā, lai šķirošanas vairāk
viss masīvs.
>> Tagad atceros, kā atlase veida darbi.
Mēs ejam, lai iet visam blokam meklē minimālo vērtību
masīvs un stick ka sākumā.
Tad mēs esam gatavojas iet pār visu masīvs atkal meklē otro
mazākais elements, un stick ka Otrajā pozīcijā
array, un tā tālāk.
Tāpēc, ka tas, ko tas dara.
>> Lūk, mēs redzam, ka mēs esam nosakot pašreizējo minimālo
vērtība i-indeksu.
Tātad uz pirmā atkārtojuma, mēs ejam apsvērt minimālā vērtība būtu
sākums mūsu masīvs.
Tad mēs spēsim atkārtot vairāk pārējā masīva, pārbaudes, lai
redzētu, vai ir kādi elementi mazāks nekā viens, ka mēs šobrīd esam
ņemot vērā minimumu.
>> Tātad šeit, vērtības J plus viens - tas ir mazāk, nekā tas, ko mēs pašlaik
ņemot vērā minimumu.
Tad mēs ejam atjaunināt ko mēs domājam, ir minimums, lai
indekss j plus 1.
Tātad, darīt pāri visam blokam, un pēc tam, lai cilpa, minimālo
jābūt vismaz elements no i-th pozīciju masīvā.
>> Pēc tam, kad mēs esam, ka mēs varam mijmaiņas minimālā vērtība uz i-tajā pozīcijā
masīvā.
Tāpēc tas ir tikai standarta swap.
Mēs uzglabāt pagaidu vērtības - i-tā vērtība masīvs -
laiž i-vērtības masīvā minimālā vērtība, kas pieder tur,
un pēc tam uzglabāt atpakaļ, kad current minimālā vērtība, ko izmanto, lai būtu
i-tā vērtība masīvs, tāpēc ka mums nav zaudēt to.
>> Tāpēc, ka turpinās nākamais atkārtojuma.
Mēs sākt meklēt otro minimālā vērtība un ievietojiet kas stājas
otro pozīciju.
Trešajā atkārtojuma, mēs meklējam Trešais minimālā vērtība un ievietot
ka uz trešo pozīciju, un tā līdz brīdim, kad mums ir sakārtoti masīvs.
Mans vārds ir Rob, un šī bija izvēle kārtošanas.