>> ROB Bowden: Bok, ja sam Rob.
Kako ćemo zaposliti binarno pretraživanje?
Idemo saznati.
Dakle, imajte na umu da je ta potraga idemo provesti rekurzivno.
Također se može provesti binarni pretragu iterativno, pa ako je to učinio,
to je savršeno u redu.
>> Sada prvi put, sjetimo se što Parametri za pretragu su trebali biti.
Ovdje vidimo int vrijednosti, što je bi trebala biti vrijednost korisnik
u potrazi za.
Vidimo niz int vrijednosti, koje je niz u kojem smo
u potrazi za vrijednosti.
I vidimo int n, što je Duljina našeg polja.
>> Sada, prva stvar na prvom mjestu.
Provjerili smo da li je n = 0, u čemu smo se vratili lažna.
To samo govori da se moramo prazna polje, vrijednost očito nije u
prazno polje, pa smo se vratili lažna.
>> Sada, mi zapravo želite učiniti binarni traži dio binarnog pretraživanja.
Dakle, želimo pronaći sredinu element tog niza.
Evo, mi kažemo middle jednaka n podijeljeni za 2, jer srednji element
će biti duljina naša polja podijeljena dva.
Sada ćemo provjeriti je li Srednji element koji je jednak vrijednosti koju ste
u potrazi za.
Dakle, ako vrijednosti srednje jednaka vrijednosti, mi može vratiti točno jer smo otkrili
vrijednost u našem polju.
>> Ali ako to nije bila istina, sada moramo učiniti rekurzivna
korak binarnog pretraživanja.
Moramo tražiti ni lijevo od niza ili
usred polja.
Pa evo, recimo, ako vrijednosti u sredini je manja od vrijednosti, što znači da je vrijednost
bio veći od sredine od niza.
Dakle, vrijednost mora biti na desnoj strani element koji smo upravo pogledao.
>> Dakle, ovdje, idemo u traži rekurzivno.
I mi ćemo pogledati što smo prolazu to u sekundi.
Ali ćemo tražiti da se Pravo srednjeg elementa.
I u drugom slučaju, to znači da vrijednost je manja od polovice
polje, pa idemo u potrazi za lijevo.
Sada, lijevo će biti malo lakše pogledati.
Dakle, ovdje vidimo da smo rekurzivno nazivajući pretragu, gdje je prvi
Argument je, opet, vrijednost da tražimo više.
Drugi argument će biti Niz koji smo tražili više.
I posljednji element koji je sada srednji.
Sjeti se zadnji parametar je naš int n, tako da je dužina naše polje.
>> U rekurzivni poziv za pretraživanje, mi smo Sada kaže da je duljina
Niz je srednji.
Dakle, ako naše polje je veličine 20 i mi Tražili indeksa 10, budući da je srednji
20 podijeljeno s dva, to znači da smo prolazi 10 kao nova
duljina naše polje.
Zapamtite da kada imate niz duljine 10, to znači da vrijedi
elementi su indeksa 0 do 9.
Dakle, to je upravo ono što želimo odrediti našu obnovljeno niz - lijevi
Niz od srednjeg elementa.
>> Dakle, u potrazi za pravom je malo teže.
Sada je prvi, neka je uzeti u obzir duljinu od niza s desne strane
Srednji elementa.
Dakle, ako je naš niz veličine n, tada Nova polje će biti veličine n minusu
Srednji minus 1.
Dakle, neka je razmišljati o n minus sredini.
>> Opet, ako je niz su veličine 20 i podijelimo sa 2 da se u sredini,
pa srednji je 10, a zatim n minus srednje će nam dati 10, pa 10
elementi na desnoj strani sredini.
No, imamo i ovaj minus 1, jer mi ne želimo da se
uključuju samu sredinu.
Dakle n minus srednji minus 1 nam daje ukupni broj elemenata na desnoj strani
srednjeg indeksa u nizu.
>> Sada ovdje, ne zaboravite da je srednji parametar je polje vrijednosti.
Pa evo, mi smo prolazu izmijenjena vrijednosti polja.
Ovaj vrijednosti plus srednje plus 1 je zapravo govori rekurzivno poziva
pretraživanje, prolazi u novom ruhu, gdje da je novi niz počinje u sredini
plus jedan je od naše izvorne vrijednosti niza.
>> Alternativna sintaksa za to, sad kad vi ste počeli vidjeti naputke, je
Ampersand vrijednosti srednje plus 1.
Dakle, zgrabite adresu sredini plus jedan element vrijednosti.
>> Sada, ako nije bilo ugodno modificiranje niz kao što je to, što
također mogao provesti to pomoću rekurzivna funkcija pomagač, gdje
da pomagač funkcije traje više argumenata.
Dakle, umjesto da samo vrijednost, polje, a veličina polja,
pomagač funkciju mogao uzeti više argumenata, uključujući i donji indeksa
da bi stalo u nizu i gornji indeks da ti je stalo
o nizu.
>> I tako praćenje i manja index i gornji indeks, ne znaš
morati sve mijenjati izvorne vrijednosti polja.
Možete samo nastaviti koristiti niz vrijednosti.
Ali ovdje, primijetit ne trebamo pomagač funkcionirati dokle god smo
spremni mijenjati original Vrijednosti polja.
Mi smo spremni da prođe u Ažurirani vrijednosti.
>> Sada, ne možemo binarni pretragu Niz je to nerazvrstani.
Dakle, neka je dobiti ovaj izdvojiti.
Sada, primijetiti da je sorta je posljednje dvije Parametri int vrijednosti, što je
Niz da sređujemo, a int n, što je duljina niza koji
sređujemo.
Dakle, ovdje želimo provesti sortiranje algoritam
da je o n na kvadrat.
Možete odabrati bubble sortiranje, odabir sortiranje ili umetanje vrsta, ili
neka druga vrsta nemamo Vidio je u klasi.
Ali ovdje, idemo u Koristi odabir vrsta.
>> Dakle, mi ćemo ponoviti tijekom cijelog niza.
Pa, ovdje vidimo da smo iterating od 0 do N minus 1.
Zašto ne skroz do n?
Pa, ako smo već razvrstani prvi n minus 1 elementi, zatim
posljednji element koji ono mora biti već na pravo mjesto, tako da tijekom sortiranja
Cijeli niz.
>> Sad, sjetite se kako je izbor vrsta radova.
Mi ćemo ići preko cijelog niza u potrazi za minimalne vrijednosti u
polje i stick koji na početku.
Onda ćemo ići preko cijelog Niz opet u potrazi za sekundu
najmanji element, a stick koji u drugom položaju u
polje, i tako dalje.
Dakle, to je ono što ovaj radi.
>> Evo, mi smo vidjeli da smo postavljanje trenutni minimum
vrijednost i-tog indeksa.
Dakle, na prvoj iteraciji, idemo uzeti u obzir minimalna vrijednost biti
Početak našeg niza.
Zatim ćemo ponoviti tijekom Preostali dio polja, provjeravajući
vidi ima li kakvih elemenata manji od onaj koji smo trenutno
s obzirom na minimum.
>> Pa evo, vrijednosti j plus jedan - to je manje od onoga što smo mi sada
s obzirom na minimum.
Onda ćemo ažurirati što mi mislimo da je minimalno za
indeks j plus 1.
Dakle, to učiniti preko cijelog niza, , a nakon toga za petlje, minimum
trebao biti minimalan element iz i-ti položaj u nizu.
>> Nakon što smo to, možemo mijenjati Minimalna vrijednost u i-tom položaju
u polju.
Dakle, ovo je samo standardni swapa.
Mi pohraniti u privremenu vrijednosti - i-vrijednost u polju -
staviti u i-tom vrijednosti u polju Minimalna vrijednost koja pripada tamo,
a potom pohraniti natrag u kojoj Trenutna minimalna vrijednost koja se koristi kako bi se
i-vrijednost u polju, pa da nismo izgubili.
>> Dakle, da se nastavlja Sljedeća iteracija.
Mi ćemo početi tražiti drugi Minimalna vrijednost i umetnite ga u
drugo mjesto.
Na trećoj iteraciji, mi ćemo tražiti Treći minimalna vrijednost i umetak
da u treći položaj, i tako sve dok imamo sortirani niz.
Moje ime je Rob, a to bio izbor vrsta.