Binární vyhledávání je jedním z nejjednodušších způsobů, jak najít prvek v poli

Programátoři, dokonce i začátečníci, často čelí skutečnosti, že existuje řada čísel, ve kterých je nutné určit určité číslo. Tato sbírka se nazývá pole. A najít správný prvek v něm, existuje spousta způsobů. Ale nejjednodušší z nich vpravo lze považovat za binární vyhledávání. Jaká je metoda? A jak implementovat binární vyhledávání? Pascal je nejsnadnějším prostředkem pro organizaci takového programu, takže jej využijeme ke studiu.

Za prvé budeme analyzovat, jaké výhody této metody jsou, koneckonců, abychom pochopili, jaký je smysl pro studium tohoto 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, jaký je princip této metody? Za zmínku stojí, že binární vyhledávání nefunguje v žádném poli, ale pouze v tříděné sadě čísel. Při každém dalším kroku se provede středový prvek pole (s odkazem na číslo prvku). Pokud požadované číslo více znamená to, že všechno, co je vlevo, tedy méně než průměrný prvek, může být zahozeno a nehledáno tam. Naopak, pokud je nižší než průměr, mezi čísly na pravé straně je nemůžete hledat. Dále vybereme novou oblast hledání, kde střední prvek celého pole bude prvním prvkem a ten poslední zůstane poslední. Průměrný počet nových oblastí bude frac14- celé délce, 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í.

binární vyhledávání pascal

Samozřejmě, je nejlepší podívat se na příklad toho, jak je napsáno binární vyhledávání. Pascal zde je vhodný pro každého - verze není důležitá. Napište jednoduchý program.

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

Takže nejprve přiřaďte horní a dolní hranice vyhledávacího intervalu:

niz: = 1-
verh: = h + 1;

Pak uspořádáme cyklus "zatímco dno je menší než horní mez":

Zatímco niz < verh - 1
začít

V každém kroku rozdělujte segment o 2:

sredn: = (niz + verh) div 2- {použijte funkci div, protože rozdělujeme zbytek}

Pokaždé, když provádíme kontrolu. Pokud se průměr rovná požadované hodnotě, přerušíme cyklus, jelikož již nalezen požadovaný element:

pokud sredn = isk pak break;

Pokud je průměrný prvek pole větší než ten, který hledáme, vyhoďte levou stranu, to znamená, že přiřadíme střední prvek k horní hranici:

pokud massiv [sredn]> isk pak verh: = sredn;

A pokud naopak, uděláme to dolní hranici:

jiný niz: = sredn-
konec;