Bináris keresés - az egyik legegyszerűbb módja, hogy megtalálják egy elem egy tömb

Elég gyakran, programozók, még a kezdők, szembesülnek azzal a ténnyel, hogy van egy számsor, ami kell találni egy adott számot. Ez a gyűjtemény az úgynevezett egy tömbben. És megtalálni azokat az elemeket benne, van számtalan módon. De a legegyszerűbb közülük lehet tekinteni a bináris keresés a jobb oldalon. Mi ez a módszer? És hogyan hajtsák végre a bináris keresés? Pascal a legegyszerűbb környezet a szervezet egy ilyen program, így fogjuk használni, hogy tanulmányozza.

Először is, elemezni, mi az előnye ennek a módszernek, hogy így meg tudjuk érteni, mi az a pont, a tanulmány a téma. Tehát, vessünk egy tömb mérete legalább 100000000 elemek, amelyeket meg kell találni. Természetesen ez a probléma könnyen megoldható egy egyszerű lineáris keresés, amelyben mi használ a ciklus lesz összehasonlítani kívánt elem mindazokkal, amelyek a tömb. A probléma az, hogy a végrehajtása ezt az ötletet vesz túl sok időt. Egy egyszerű Pascal programot több alkalommal, és három sor a fő szöveg, akkor nem veszi észre, de ha jön egy többé-kevésbé nagy projektek számos ága és a jó funkcionalitás, a program lesz bepakolásukra túl sokáig. Különösen, ha a számítógép egy gyenge teljesítmény. Ezért van egy bináris keresés, ami csökkenti a keresési idő legalább kétszer.

Szóval, mi a működési elve az ezt a módszert? Azonnal meg kell mondani, hogy a bináris keresés működik, nem minden tömb, de csak egy rendezett számsor. Minden lépésnél figyelembe közepén eleme a tömb (ami az az elem számát). Ha a szükséges szám nagyobb, mint az átlag, akkor nem marad más hátra, ami kevesebb, mint az átlagos cella, el lehet dobni, és nem néz oda. Ezzel szemben, ha kevesebb, mint az átlag - többek között ezek a számok a jobb, nem kereshet. Ezután válasszuk ki az új keresési terület, ahol az első elem lesz a középső eleme az egész tömböt, és az utolsó és az utolsó lesz. Az átlagos száma az új mező lesz ¼ az összes szegmens, azaz (az utolsó elem + középső eleme a teljes tömb) / 2. Ismét, ugyanazt a műveletet végezzük - összehasonlítás átlagos számát a tömb. Ha a cél-érték kevesebb, mint az átlagos, elutasítjuk a jobb oldalon, és azt is, hogy a következő lépés, eddig ez a középső elem nem kívánatos.

Persze, a legjobb, hogy nézd meg egy példát, hogyan kell írni a bináris keresés. Pascal itt fog felelni bárki - verzió nem fontos. Írjunk egy egyszerű program.

Ez egy sor 1 H néven „Massiv”, egy változó jelzi az alsó határa a keresési, az úgynevezett „NIZ”, a felső határ, az úgynevezett „verh”, az átlagos keresési kifejezés - „sredn”; és a szükséges számú - „isk”.

Tehát először rendelünk az alsó és felső határa közötti keresés:

NIZ: = 1;
verh: = h + 1;

Majd úgy szervezni a ciklus „amíg az alsó kisebb, mint a felső határ”:

Míg NIZ kezdődik

Minden lépésben elosztjuk a szegmens 2:

sredn: = (NIZ + verh) div 2; {A funkció div, mert a szakadék maradék nélkül}

Minden ellenőrzés időpontjában. Mivel a tétel már találni, ha a közeg kívánatos, szakítsa ciklus:

іf sredn = ISK majd a szünet;

Ha a középső elem a tömb több mint kívánt, dobja ki a bal oldalon, azaz a felső határ az átlagos nevez elem:

ha massiv [sredn]> ISK majd verh: = sredn;

És ha éppen ellenkezőleg, ez teszi az alsó határ:

mást NIZ: = sredn;
végén;

Ez minden, ami lesz a programban.

Nézzük meg, hogyan fog kinézni a bináris módszer a gyakorlatban. Tekintsük ez a tömb: 1, 3, 5, 7, 10, 12, 18, és arra törekszik, a 12-es szám.

Összesen van 7 eleme, így lesz a negyedik közeg, az érték 7.

Mivel több, mint 12, 7, 1,3 és 5 elem, akkor dobja. Akkor megvan a 4-es számú, 4/2 nincs maradék 2. Tehát egy új elem lesz átlagosan 10.

12. óta nagyobb, mint 10, akkor dobja 7. Továbbra is csak 10, 12 és 18.

Itt a középső elem már 12, akkor a kívánt számot. Ezt a feladatot teljesíti - 12-es szám található.