>> ZAMYLA Chan: Az első dolog, amit értesítést találni, hogy már
már kódot írt nekünk.
Ez az úgynevezett elosztási kód.
Szóval nem csak írásban, a saját kódot a semmiből többé.
Inkább mi kitöltésével üregek néhány már meglévő kódot.
>> A beolvasása sikertelen program rákérdez a számok , hogy töltse ki a szénakazalban, megkeresi a
szénaboglya a felhasználó benyújtott tű, és ez teszi ezt hívja a fajta és a
keresés funkciók meghatározása A helpers.c.
Tehát elérése sikertelen van írva már.
Az Ön feladata, hogy írjon segítők.
>> Szóval, mit csinálunk?
Mi végrehajtása két funkciója van.
Search, amely igazat ad vissza, ha az érték megtalálható a szénakazalban, visszatérő
hamis, ha az érték nem a szénakazalban.
És akkor mi is végrehajtási sort, amely rendezi a tömb neve értékeket.
Úgyhogy kezelni keresést.
>> Keresés jelenleg megvalósított lineáris keresést.
De meg tudod csinálni sokkal jobb, mint ezt.
Lineáris keresést végrehajtani O n idő, ami elég lassú, bár
lehet keresni bármilyen lista adott hozzá.
Az Ön feladata, hogy végre bináris keresés, amely a futási idő O log n.
Ez elég gyors.
>> De van egy kikötés.
Bináris keresés csak keresni a előválogatva listákat.
Miért van ez?
Nos, nézzük meg egy példát.
Mivel az értékek tömbjét, a szénakazalban, fogunk keresni
egy tűt, és ebben a Például, a 3 egész szám.
>> Az út, hogy a bináris keresés működik, hogy a összehasonlítjuk a közép értéke
A tömb a tű, ugyanúgy, mint, hogy hogyan nyitottunk egy telefonkönyvet a középső
oldal 0. héten.
Tehát miután összehasonlítva a közép-értéket a tű, akkor dobja ki vagy a
a bal vagy a jobb fele a tömb szigorításával a határokat.
Ebben az esetben, mivel 3, a mi tű van kevesebb, mint 10, a középső érték,
jobbra kötött csökkentheti.
>> De próbálja meg, hogy a határt szoros amennyire csak lehetséges.
Ha a középső érték nem a tűt, akkor tudja, hogy nem kell
tartalmazza azt a keresésben.
Tehát a jobb kötve húzza meg a Keresés korlátok csak egy kicsit nagyobb,
és így tovább és így tovább, amíg megtalálni a tűt.
>> Tehát mit csinál az ál code néz ki?
Nos, míg mi még mindig keresi a a listát, és még
elemeket, hogy vizsgálja meg, vesszük a középső a lista, és hasonlítsa össze, hogy
közepes értéket a tűt.
Ha ők azonos, akkor ez azt jelenti, hogy már találta a tűt, és mi is
vissza igaz.
>> Ellenkező esetben, ha az kisebb, mint a tű a középső érték, akkor ez azt jelenti,
eldobhatja a jobb fele, és csak keresés a bal oldalán a tömb.
Ellenkező esetben, akkor keresni a jobb oldalán a tömb.
És a végén, ha nincs több elem maradt keresni, de
nem találtam a tű még, akkor return false.
Mivel a tűt határozottan nem a szénakazalban.
>> Most, egy szép dolog ez a pszeudo kód bináris keresés az, hogy ez
kell értelmezni, mint akár egy iteratív vagy rekurzív végrehajtás.
Így lenne rekurzív, ha hívják A keresési funkció a keresési
működni mindkét fele a tömb.
Majd kiterjed rekurzió egy kicsit később a kurzus.
De tudom, hogy ez egy lehetőség ha szeretnéd kipróbálni.