>> ROB BOWDEN: Sveiki, aš esu Robas.
Kaip mes naudojame dvejetainio paiešką?
Leiskite sužinoti.
Taigi, atkreipkite dėmesį, kad tai paieškos mes ketiname rekurencyjnego įgyvendinti.
Jūs taip pat galėtų įgyvendinti binarinę paiešką keletą kartų, todėl, jei jums padarė, kad
tai puikiai baudą.
>> Dabar pirmiausia, galime prisiminti, kas parametrai ieškoti yra skirta būti.
Čia mes matome, int verte, kuri yra turėtų būti vertė vartotojas
ieško.
Matome int reikšmių masyvą, kuris yra matrica, kurioje mes
ieškoti vertę.
Ir mes matome, int n, kuris yra mūsų masyvo ilgis.
>> Dabar pirmas dalykas pirmas.
Mes patikrinti, ar n lygus 0, ir tokiu atveju mes return false.
Tai tiesiog pasakyti, jei mes turime tuščias masyvas, vertė yra akivaizdžiai ne
tuščias masyvas, todėl mes galime grįžti klaidinga.
>> Dabar mes iš tikrųjų nori daryti dvejetainis paieška dalis dvejetainėje paiešką.
Taigi, mes norime rasti vidurį elementas šiame masyve.
Štai, mes sakome, viduriniosios Lygu n suskirstyti 2, nes viduryje elementas yra
bus iš ilgis mūsų masyvas padalintas iš 2.
Dabar mes ketiname patikrinti, ar viduryje elementas yra lygi vertei, kurias mes
ieško.
Taigi, jei vertės viduryje Lygu vertę, mes gali grįžti tiesa, nes mes radome
vertė mūsų masyvo.
>> Bet jei tai buvo tiesa, dabar mes turime padaryti, grįžtamojo
žingsnis dvejetainėje paiešką.
Mums reikia ieškoti arba į paliko masyvo arba
viduryje masyvo.
Taigi čia mes sakome, jei vertes viduryje yra mažiau nei vertės, tai reiškia, kad tą vertę
buvo didesnis nei viduryje masyvo.
Taigi, vertė turi būti į dešinę elementas, kad mes tik pažvelgė.
>> Taigi čia mes ketiname ieškoti rekursyviai.
Ir mes pažvelgti į tai, ką mes artimųjų tai per sekundę.
Tačiau mes ketiname ieškoti į teisė viduryje elementas.
O kitu atveju, tai reiškia, kad vertė buvo mažesnė nei viduryje
masyvas, todėl mes ketiname ieškoti į kairę.
Dabar, kairėje bus tiek lengviau pažvelgti.
Taigi, matome, kad čia mes rekursyviai telefonu paiešką, kur pirmasis
argumentas yra, vėlgi, vertė mes ieškome daugiau.
Antrasis argumentas bus matrica, ieškojome naujo.
Ir paskutinis elementas dabar yra viduryje.
Prisiminti paskutinis parametras yra mūsų int n, todėl tai mūsų masyvo ilgis.
>> Be grįžtamojo skambučio ieškoti, mes dabar sako, kad ilgis
masyvas yra viduryje.
Taigi, jei mūsų masyvas buvo 20 dydžio, ir mes ieškoma 10 indeksą, nes viduryje yra
20 padalinti iš 2, tai reiškia, kad mes einančios 10 kaip nauja
ilgis mūsų masyvo.
Atminkite, kad kai jūs turite masyvą ilgis 10, tai reiškia, kad galioja
elementai yra indeksų 0 iki 9.
Taigi tai yra būtent tai, ko mes norime nurodyti atnaujintą mūsų masyvas - kairįjį
masyvas iš viduriniosios elementas.
>> Taigi, žiūrint į dešinę yra šiek tiek sunkiau.
Dabar pirmiausia aptarkime ilgį iš į dešinę masyvo
viduryje elementas.
Taigi, jei mūsų masyvas buvo dydžio n, tada nauja matrica bus dydis n minus
vidutinio atėmus 1.
Taigi, galime galvoti apie n minuso viduryje.
>> Vėlgi, jei masyvas buvo dydžio 20 ir mes padalinti iš 2 gauti vidurį,
taip viduryje yra 10, tada n atėmus vidutinio ketina duoti mums 10, taigi 10
elementai į vidurį dešinėje.
Bet mes taip pat turime šį minusą 1, nes mes nenorime
įtraukti vidurį pati.
Taigi n atėmus vidutines atėmus 1 suteikia mums bendras elementų skaičius į dešinę
viduriniosios indeksas masyve.
>> Dabar čia, atminkite, kad vidutinio parametras yra vertės masyvo.
Taigi čia mes artimųjų atnaujinama vertės masyvo.
Šis vertės plius viduriniosios plius 1 yra faktiškai sakydamas rekursyviai skambinti
paieška, einančios į naują masyvą, kur kad naujasis masyvas prasideda viduryje
plius vienas iš mūsų pradines reikšmes masyvo.
>> Pakaitinis sintaksė, kad dabar, jūs pradėjote matyti patarimų, yra
Ampersand vertės viduryje plius 1.
Taigi, patraukti viduryje adresą plius vienas elementas vertybes.
>> Dabar, jei jums buvo ne patogus keitimo, kaip kad masyvas, jūs
Taip pat galėjo būti įgyvendintas šis naudojant rekursywny pagalbininkas funkcija, kur
kad pagalbininkas funkcija trunka daugiau argumentų.
Taigi vietoj to, reikia atsižvelgti tik į vertę, masyvas ir masyvo dydis,
pagalbininkas funkcija galėtų būti daugiau argumentai, įskaitant apatinės rodyklės
kad jūs rūpi masyve ir viršutinis indeksas, kad jums rūpi
apie masyve.
>> Ir taip nuolat stebėti tiek mažesnis indeksas ir viršutinis indeksas, jūs neturite
reikia nuolat keisti pradines reikšmes masyvo.
Jūs galite tiesiog toliau naudoti reikšmių masyvą.
Bet čia, pranešimas, mums nereikia pagalbininkas veikti tol, kol mes
nori pakeisti originalą vertės masyvo.
Mes pasirengę praeiti Atnaujinta vertės.
>> Dabar, mes negalime binarinę paiešką per matrica, yra pramaišiui.
Taigi, galime gauti tai sutvarkyti.
Dabar pastebime, kad rūšiuoti pastaruosius dvejus parametrai int vertybes, kurios yra
matrica, mes rūšiavimo ir int n, kuris yra masyvo ilgis, kad
mes rūšiavimas.
Taigi, čia mes norime įgyvendinti rūšiavimo algoritmas
kad yra o n kvadratu.
Jūs galite pasirinkti burbulas rūšiavimo, atrankos rūšiuoti, ar įterpimo rūšiuoti, arba
kai kitos rūšies turime ne matyti klasėje.
Bet čia mes ketiname naudoti atrankos rūšiuoti.
>> Taigi, mes ketiname pakartoti pagal visą gardelę.
Na, čia mes matome, kad mes Iteracja nuo 0 iki n atėmus 1.
Kodėl ne visi kelią iki n?
Na, jei mes jau rūšiuojami pirma n minus 1 elementai, tada
paskutinis elementas, kas jau turi būti yra teisingoje vietoje, todėl rūšiavimo per
Visas masyvo.
>> Dabar prisimenu, kaip pasirinkimas rūšiuoti veikia.
Mes ketiname eiti per visą gardelę, ieško minimalios vertės
masyvas ir lazdas, kad pradžioje.
Tada mes ketiname eiti per visą masyvas vėl ieško sekundę
mažiausias elementas, ir lazdas, kad antroje padėtyje
masyvas ir tt.
Taigi, tai, kas tai daro.
>> Čia mes matome, kad mes nustatant dabartinius minimalius
vertė i-tojo indekso.
Taigi pirmajame iteracijos, mes ketiname apsvarstyti minimali vertė turi būti
mūsų masyvo pradžia.
Tada mes ketiname pakartoti per likusi masyvo, patikrinti,
pamatyti, jei yra kokių nors elementų mažesnis nei vienas, kad mes šiuo metu
atsižvelgiant į minimalų.
>> Taigi čia, vertybės j plius vienas - tai mažiau nei tai, ką mes šiuo metu
atsižvelgiant į minimalų.
Tada mes ketiname atnaujinti kas mes manome, kad yra minimumas
j indeksas plius 1.
Taigi, tai, kad per visą gardelę, ir po to už kilpos, mažiausiai
turėtų būti minimalus elementas iš i-asis pozicija masyve.
>> Kai mes turime, kad galėtume sukeisti minimali vertė į i-osios pozicijos
masyve.
Taigi tai yra tik standartinis apsikeitimo.
Mes laikyti laikina verte - i-asis vertė masyve -
įdėti į i-osios vertės masyvo minimali vertė priklauso ten,
ir tada laikyti atgal į kur anksčiau dabartinė minimali vertė
i-asis vertė masyve, todėl kad mes ne prarasti.
>> Taigi, kad ir toliau nuo kitą iteracijos.
Pradėsime ieško sekundę minimali vertė ir įterpkite į
Antroji pozicija.
Trečią iteracijoje mes ieškome Trečiasis minimali vertė ir įterpti
kad į trečią vietą, ir taip tol, kol mes turime surūšiuotą masyvo.
Mano vardas yra Rob, o tai buvo pasirinkimas rūšiuoti.