Gyakran a programozók, még a kezdők is,szembesülve azzal a ténnyel, hogy létezik olyan számkészlet, amelyben meg kell találnia egy bizonyos számot. Ezt a gyűjteményt tömbnek hívják. És hogy megtalálják a kívánt elemet benne, hatalmas különféle lehetőségek vannak. De a legegyszerűbbek között jogosan tekinthető bináris keresésnek. Mi az adott módszer? És hogyan lehet végrehajtani a bináris keresést? A Pascal a legkönnyebb környezet egy ilyen program megszervezéséhez, ezért tanulmányozásra használjuk.
Először megvizsgáljuk ennek a módszernek az előnyeit, mert megértjük
Szóval, mi az ennek alapelvemódszer? Érdemes rögtön mondani, hogy a bináris keresés egyetlen tömbben sem működik, hanem csak egy rendezett számkészletben. Minden következő lépésben a tömb középső elemét vesszük (az elem számával értve). Ha a kívánt szám nagyobb, mint az átlag, akkor minden, ami a bal oldalon van, azaz kevesebb, mint a középső elem, elvethető és ott nem kereshető. Ezzel szemben, ha az átlagnál kevesebb - a jobb oldali számok között nem lehet keresni. Ezután kiválasztunk egy új keresési területet, ahol az első elem a teljes tömb középső elemét, az utolsó pedig az utolsó marad. Az új régió átlagos száma a teljes szegmens ¼-je, azaz (az utolsó elem + a teljes tömb középső eleme) / 2. Ugyanezt a műveletet hajtjuk végre - összehasonlítva a tömb átlagos számával. Ha a kívánt érték alacsonyabb, mint az átlag, akkor dobjuk el a jobboldalt, és végezzük ugyanezt tovább, amíg ez a középső elem meg nem található.
Természetesen a legjobb, ha egy példát nézünk a bináris keresés írására. A Pascal bárki számára alkalmas - a verzió nem fontos. Írjunk egy egyszerű programot.
1-től h-ig terjedő tömb lesz"massiv", a keresés alsó határát jelölő "niz", a felső határot "verh", a keresés középső elemét "sredn" jelöli; és a kívánt számot ISK.
Tehát először hozzárendeljük a keresési intervallum felső és alsó határait:
alsó: = 1;
verh: = h + 1;
Ezután megszervezzük a ciklust "míg az alsó kevesebb, mint a felső határ":
Amíg niz
Minden szakaszban ossza meg a szegmenst 2-del:
sredn: = (niz + verh) 2. rész; {használja a div függvényt, mert maradék nélkül osztjuk szét}
Minden alkalommal, amikor ellenőrizünk. Ha az átlag a kívánt, akkor megszakítjuk a ciklust, mivel a kívánt elemet már megtaláltuk:
ha sredn = isk, akkor szakítsa meg;
Ha a tömb középső eleme nagyobb, mint a kívánt, akkor a bal oldalt eldobjuk, vagyis a középső elemet a felső határhoz rendezzük:
ha tömb yusrednsch> pert pert: = átlag;
És ha éppen ellenkezőleg, akkor alsóbbá tesszük:
else niz: = sredn;
végén;
Ez minden, ami a programban lesz.
Lássuk, hogyan fog kinézni a bináris módszer a gyakorlatban. Vegyünk egy ilyen tömböt: 1, 3, 5, 7, 10, 12, 18, és a 12-es számot fogjuk keresni benne.
Összességében 7 elem van, tehát a negyedik lesz az átlag, értéke 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Mivel a 12 nagyobb, mint 7, elvehetjük az 1,3 és 5 elemeket. Akkor 4 szám marad, 4/2 maradék nélkül 2. Tehát az új középső elem 10 lesz.
| 7 | 10 | 12 | 18 |
Itt a középső elem már 12, ez a kívánt szám. A feladat befejeződött - 12. szám talált.
