Binární vyhledávání vs lineární vyhledávání
Lineární vyhledávání, známé také jako sekvenční vyhledávání, je nejjednodušší vyhledávací algoritmus. Vyhledává zadanou hodnotu v seznamu kontrolou každého prvku v seznamu. Binární vyhledávání je také metoda používaná k nalezení zadané hodnoty v seřazeném seznamu. Binární metoda vyhledávání snižuje počet kontrolovaných prvků na polovinu (v každé iteraci), čímž zkracuje čas potřebný k nalezení dané položky v seznamu.
Co je lineární vyhledávání?
Lineární vyhledávání je nejjednodušší metoda vyhledávání, která postupně kontroluje každý prvek v seznamu, dokud nenajde zadaný prvek. Vstupem do metody lineárního vyhledávání je sekvence (jako je pole, kolekce nebo řetězec) a položka, kterou je třeba prohledat. Výstup je pravdivý, pokud je zadaná položka v zadané posloupnosti, nebo nepravda, pokud v posloupnosti není. Protože tato metoda kontroluje každou položku v seznamu, dokud není zadaná položka nalezena, v nejhorším případě projde všechny prvky v seznamu, než najde požadovaný prvek. Složitost lineárního vyhledávání je o(n). Proto je považován za příliš pomalý na to, aby byl použit při vyhledávání prvků ve velkých seznamech. Ale je to velmi jednoduché a snadněji implementovatelné.
Co je binární vyhledávání?
Binární vyhledávání je také metoda používaná k nalezení zadané položky v seřazeném seznamu. Tato metoda začíná porovnáním hledaného prvku s prvky uprostřed seznamu. Pokud porovnání určí, že jsou dva prvky stejné, metoda se zastaví a vrátí polohu prvku. Pokud je hledaný prvek větší než prostřední prvek, spustí metodu znovu pouze pomocí spodní poloviny seřazeného seznamu. Pokud je hledaný prvek menší než prostřední prvek, spustí metodu znovu pouze pomocí horní poloviny seřazeného seznamu. Pokud hledaný prvek není v seznamu, metoda vrátí jedinečnou hodnotu, která to indikuje. Proto metoda binárního vyhledávání snižuje počet porovnávaných prvků na polovinu (v každé iteraci) v závislosti na výsledku porovnání. V důsledku toho binární vyhledávání probíhá v logaritmickém čase, což vede k průměrnému výkonu o(log n).
Jaký je rozdíl mezi binárním vyhledáváním a lineárním vyhledáváním?
Přestože jak lineární, tak binární vyhledávání jsou způsoby vyhledávání, mají několik rozdílů. Zatímco binární vyhledávání funguje na seřazených seznamech, liniové vyhledávání může fungovat i na nesetříděných seznamech. Řazení seznamu má obecně průměrnou složitost n log n. lineární vyhledávání je jednoduché a přímočaré na implementaci než binární vyhledávání. Lineární vyhledávání je však příliš pomalé na to, aby jej bylo možné použít s velkými seznamy, a to kvůli jeho o(n) průměrnému výkonu. Na druhou stranu je binární vyhledávání považováno za efektivnější metodu, kterou lze použít u velkých seznamů. Implementace binárního vyhledávání však může být poměrně složitá a studie ukázala, že přesný kód pro binární vyhledávání lze nalézt pouze v pěti z dvaceti knih.
