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.