>> ROB BOWDEN: Szia, én vagyok Rob.
Hogy mi foglalkoztat egy bináris keresést?
Nézzük meg.
Tehát, vegye figyelembe, hogy ez a keresés megyünk végrehajtása rekurzívan.
Te is végre bináris keresés iteratív módon, tehát, ha azt tenné,
ez tökéletesen megfelel.
>> Most először, ne felejtsük el, amit a paramétereket a keresés célja, hogy.
Itt látjuk int érték, ami állítólag az érték a felhasználó
keres.
Látjuk a int értékeket tömb, amely az a tömb, amelyben vagyunk
keresett értéket.
És azt látjuk, int n, ami a hossza a tömb.
>> Nos, az első dolog az első.
Ellenőrizzük, hogy ha n értéke 0, a mely esetben return false.
Ez csak azt mondom, ha van egy üres tömb értéke nyilvánvalóan nem egy
üres tömböt, így is vissza hamis.
>> Most valóban szeretné ezt a bináris keresés része a bináris keresés.
Tehát, meg akarjuk találni a közepén eleme a tömb.
Itt mondjuk közepes értéke n megosztott 2-vel, mivel a középső elem
lesz a hossza a tömb osztva 2-vel.
Most megyünk, hogy ellenőrizze, hogy a középső elem megegyezik az értéket vagyunk
keres.
Tehát, ha értéke közepén egyenlő értéket, akkor Visszatérhet igaz, mert megtaláltuk a
érték a tömbben.
>> De ha ez nem volt igaz, most meg kell csinálni a rekurzív
lépése bináris keresés.
Meg kell keresni, hogy vagy a elhagyta a tömb vagy a
közepén a tömb.
Tehát itt, azt mondják, ha értékeket középen kisebb érték, azt jelenti, hogy értéke
nagyobb volt, mint a középső a tömb.
Így érték kell, hogy legyen, hogy a jobb oldalon a elem, hogy csak nézett.
>> Tehát itt, megyünk keresés rekurzívan.
És nézzük meg, amit mi halad ehhez a második.
De fogunk keresni, hogy a jobb a középső elem.
És a másik esetben, ami azt jelenti, hogy a értéke kisebb volt, mint a közepén, a
tömb, és így megyünk keresni a bal oldalon.
Most a bal oldali lesz egy kicsit könnyebb nézni.
Tehát azt látjuk, hogy itt vagyunk rekurzívan hívja kereső, ahol az első
érv ismét az érték keresünk vége.
A második érv lesz a tömb kerestük vége.
És az utolsó elem most közepén.
Ne feledje, az utolsó paraméter az int n, hogy ez a hossza a tömb.
>> A rekurzív hívás keresni, vagyunk most azt mondja, hogy a hossza a
tömb közepén.
Tehát, ha a tömb volt a mérete 20 és keresni az index 10, mivel a középen
20 osztva 2, ez azt jelenti, nem vagyunk 10 halad, mint az új
hossza a tömb.
Ne feledje, hogy ha van egy tömb A hossz 10, azt jelenti, hogy az érvényes
vannak-indexek 0-tól 9.
Tehát pontosan ez az, amit akarunk adja meg a frissített tömb - a baloldali
tömb a középső elem.
>> Tehát, akik a jog egy kicsit nehezebb.
Most először, nézzük meg a hosszát a tömb jobbra a
középső elem.
Tehát, ha a tömb volt méretű n, akkor a új tömb lesz n méretű mínusz
közepén mínusz 1.
Szóval, most gondolj n mínusz közepén.
>> Ismét, ha a tömb mérete 20 voltak, és osztunk 2, hogy a közép-,
így a középső 10, akkor n mínusz közepén megy, nekünk 10, azaz 10
elemek jobbra közepén.
De mi is ez a mínusz 1., mert nem akarjuk, hogy
többek között a középső is.
Tehát n mínusz közepén mínusz 1 megadja a száma elemek megfelelő
a középső index a tömbben.
>> Most itt van, ne feledje, hogy a középső paraméter az értékeket tömb.
Tehát itt, most leadott frissített értékeket tömb.
Ez az érték, plusz középen plusz 1 valójában mondani rekurzív hívás
keresés, átadva az új tömb, ahol a hogy az új tömb közepén kezdődik
és az egyik az eredeti értékek tömb.
>> Egy alternatív szintaxist, hogy most, hogy már kezdett látni mutatók, az
jel értékek közepes plusz 1.
Szóval, fogd a címet a középső plusz egy eleme értékeket.
>> Most, ha nem kényelmes módosítása egy tömböt, mint, hogy
is hajtották végre ezt a rekurzív segítő funkció, ahol a
hogy a segítő függvény több paramétert.
Tehát ahelyett, hogy csak az érték, annál tömb, és a mérete a tömb,
A segítő funkció is, hogy több érvek, beleértve az alsó index
hogy Ön is törődnek a tömbben és a felső index, hogy érdekel
a tömb.
>> És így nyomon követése mind az alsó index és a felső index, akkor nem
kell, hogy valaha is módosítani a eredeti értékeket tömb.
Tudod csak tovább Az opció értéke tömb.
De itt, észre nem kell egy segítő működik, amíg mi vagyunk
hajlandó, hogy módosítja az eredeti értékeket tömb.
Vagyunk hajlandóak átadni frissített értékeket.
>> Nos, nem tudjuk bináris keresés vége egy tömböt, ami rendezetlen.
Szóval, most e válogatni ki.
Most veszi észre, hogy a fajta az elmúlt két int paraméterek értékeit, amely a
array, hogy mi válogatás, és int n, amely a hossza a tömb
mi válogatás.
Szóval, itt akarunk végrehajtani a rendezési algoritmus
hogy o n a négyzeten.
Lehet választani bubble sort, a kiválasztás sort, vagy beillesztés sort, vagy
valamilyen más fajta mi nem látott az osztályban.
De itt, fogunk használata kiválasztás sort.
>> Így megyünk iterációkhoz az egész tömb.
Nos, itt azt látjuk, hogy mi iterációjával n 0-tól mínusz 1.
Miért nem egészen n-ig?
Nos, ha már sorrendje az első n mínusz 1 elem, akkor az
utolsó elem, amit meg már a megfelelő helyre, így a válogatás több mint
az egész tömböt.
>> Nos, emlékszem, milyen kiválasztás sort működik.
Fogunk menni az egész tömb keresi a minimum érték
a tömb és a botot, hogy az elején.
Ezután fogunk menni az egész array ismét keresi a második
legkisebb elem, és a bot, hogy a második helyzetben a
tömb, és így tovább.
Nos, ez az, amit ez csinál.
>> Itt látjuk, hogy mi vagyunk beállítása a jelenlegi minimális
értéke az i-edik index.
Tehát az első iteráció, megyünk hogy fontolja meg a minimális értéket, hogy
kezdetén a tömb.
Akkor fogunk végighaladni a fennmaradó tömb, ellenőrzi, hogy
nézd meg, van olyan elem kisebb Az egyik, hogy mi vagyunk jelenleg
figyelembe véve a minimum.
>> Tehát itt, értékek j plusz egy -, hogy kevesebb, mint amit mi jelenleg
figyelembe véve a minimum.
Ezután fogjuk frissíteni, milyen azt hiszem, az a minimum, hogy
index j plusz 1.
Szóval, hogy az egész tömböt, és miután ez a for ciklus, minimum
minimális legyen az elem az i-edik pozíció a tömbben.
>> Ha megvan, hogy mi lehet cserélni a minimum értéket az i-edik pozíció
a tömbben.
Tehát ez csak egy szokásos csere.
Mi tárolja ideiglenes érték - az i-edik értékét a tömbben -
helyezve az i-edik értékét az a tömbben minimális érték tartozik, ott,
majd tárolja vissza, ahol a jelenlegi minimális érték szokott lenni a
i-edik értékét a tömbben, így hogy nem vesztette el.
>> Úgy, hogy folytatódik A következő iteráció.
Fogunk kezdeni a második minimális érték, és helyezze, hogy a
második helyzetben.
A harmadik ismétlés, akkor keresni A harmadik legkisebb érték és betét
hogy a harmadik helyre, és így , amíg van egy rendezett tömbben.
A nevem Rob, és ez a volt választás sort.