Binární vyhledávání - jeden z nejjednodušších způsobů, jak najít prvek v matici

Docela často, programátoři, a to i pro začátečníky, tváří v tvář s tím, že existuje řada čísel, která musí najít určitý počet. Je to právě tato kolekce se nazývá pole. A najít předměty v něm, tam jsou nesčetné množství způsobů. Ale nejjednodušší z nich lze považovat za binární vyhledávání na pravé straně. Co je to metoda? A jak provádět binární vyhledávání? Pascal je nejjednodušší prostředí pro pořádání takového programu, takže budeme používat ke studiu.

Za prvé, analyzovat, jaké jsou výhody tohoto postupu je tak můžeme pochopit, jaký je smysl ve studiu tématu. Takže, pojďme se pole o rozměrech nejméně 100000000 prvky, které je potřeba najít některé z nich. Samozřejmě, že tento problém lze snadno vyřešit jednoduchou lineární vyhledávání, ve kterém jsme pomocí cyklu porovná požadovaný prvek s těmi, které jsou v poli. Problém je v tom, že realizace této myšlenky bude trvat příliš mnoho času. V jednoduchém Pascal programu do několika procedur a tři řádky hlavního textu, budete nevšiml, ale když jsme přišli na více či méně rozsáhlých projektů s velkým počtem poboček a dobrou funkčnost, bude program připraven k načtení příliš dlouho. Zvlášť v případě, že počítač je slabý výkon. Z tohoto důvodu je binární vyhledávání, což snižuje čas při vyhledávání nejméně dvakrát.

Takže, co je pracovní princip této metody? Ihned je třeba říci, že binární hledání práce není v žádném poli, ale pouze na tříděný sadu čísel. V každém kroku přijata středního prvku matice (což znamená, že množství prvku). V případě, že požadovaný počet je vyšší, než je průměr, pak vše, co je vlevo, která je menší než běžná buňka, může být zlikvidován, nesmí se tam dívat. A naopak, je-li menší než je průměr - mezi těmito čísly na pravé straně, nemůžete vyhledávat. Potom zvolte novou vyhledávací prostor, kde bude první element být střední prvek celé pole a poslední a poslední vůle. Průměrný počet nového pole bude ¼ všech segmentu, to znamená, že (poslední prvek + prostřední prvek celé pole) / 2. Opět platí, že se provede stejná operace - srovnání s průměrným počtem pole. V případě, že cílová hodnota je nižší než průměr, odmítáme na pravé straně, a také dělat dál, dokud se tento prostřední element by nebylo žádoucí.

Samozřejmě, že je nejlepší podívat se na příklad, jak psát binární vyhledávání. Pascal zde bude vyhovovat nikomu - verze není důležité. Pojďme napsat jednoduchý program.

To je pole 1 až h pod názvem „masivu“, proměnná označující dolní hranici vyhledávání, s názvem „NIZ“, horní hranice, nazvaný „Verh“, průměrná hledaný výraz - „sredn“; a požadovaný počet - „ISK“.

Takže nejprve musíme přiřadit horní a dolní mez hledání rozsah:

NIZ: = 1;
Verh: = h + 1;

Potom uspořádat cyklus „dokud dolní část je menší než horní hranice“:

Zatímco NIZ zahájit

V každém kroku, dělíme segment 2:

sredn: = (NIZ + Verh) div 2; {Pomocí funkce div, protože dělení bez zbytku}

Pokaždé, když z přezkumu. Vzhledem k tomu, položka již bylo konstatováno, je-li to žádoucí médium, přerušení cyklu:

іf sredn = ISK pak zlomit;

V případě, že prostřední prvek pole více než je žádoucí, vyřadit na levé straně, to znamená, že horní hranice průměru jmenovat prvku:

pokud MASSIV [sredn]> ISK pak Verh: = sredn;

A je-li naopak, to je spodní hranice:

jiný NIZ: = sredn;
skončit;

To je vše, co bude v programu.

Uvažujme, jak to bude vypadat binární metody v praxi. Vezměme si tento pole: 1, 3, 5, 7, 10, 12, 18, a to se bude snažit číslo 12.

Celkem máme 7 prvky, takže bude čtvrtá médium, hodnota 7.

Vzhledem k tomu, více než 12, 7, 1,3 a 5 elementů, můžeme vyřadit. Pak máme číslo 4, 4/2 beze zbytku je 2. Takže nový prvek bude v průměru 10 let.

Vzhledem k tomu, 12 je větší než 10, můžeme vyřadit 7. zbývá pouze 10, 12 a 18.

Zde je prostřední element je již 12, je požadované množství. Tento úkol je splněn - číslo 12 nalezen.