Binární vyhledávání vs lineární vyhledávání
Nejjednodušším vyhledávacím algoritmem je lineární vyhledávání, známé také jako sekvenční vyhledávání. Vyhledá zadanou hodnotu v seznamu kontrolou všech prvků v seznamu. Binární vyhledávání je také metoda použitá k vyhledání zadané hodnoty v seřazeném seznamu. Metoda binárního vyhledávání snižuje počet kontrolovaných prvků na polovinu (v každé iteraci), což zkracuje čas potřebný k vyhledání dané položky v seznamu.
Co je lineární vyhledávání?
Lineární vyhledávání je nejjednodušší metoda vyhledávání, která kontroluje každý prvek v seznamu postupně, dokud nenajde zadaný prvek. Vstupem do metody lineárního vyhledávání je posloupnost (například pole, kolekce nebo řetězec) a položka, kterou je třeba prohledat. Výstup je true, pokud je zadaná položka v zadané posloupnosti, nebo false, pokud není v posloupnosti. Protože tato metoda kontroluje každou položku v seznamu, dokud není nalezena zadaná položka, v nejhorším případě projde všemi prvky v seznamu, než najde požadovaný prvek. Složitost lineárního vyhledávání je o (n). Proto je považováno za příliš pomalé na to, aby se dalo použít při vyhledávání prvků ve velkých seznamech. Ale je to velmi jednoduché a snáze implementovatelné.
Co je to binární vyhledávání?
Binární vyhledávání je také metoda použitá k vyhledání určité položky v seřazeném seznamu. Tato metoda začíná porovnáním prohledávaného prvku s prvky ve středu seznamu. Pokud porovnání určí, že dva prvky jsou stejné, metoda se zastaví a vrátí pozici prvku. Pokud je prohledávaný prvek větší než prostřední prvek, spustí metodu znovu pouze pomocí spodní poloviny seřazeného seznamu. Pokud je prohledávaný prvek menší než prostřední prvek, spustí metodu znovu pomocí pouze horní poloviny seřazeného seznamu. Pokud hledaný prvek není v seznamu, vrátí metoda jedinečnou hodnotu, která to naznačuje. 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í. Tudíž,binární vyhledávání probíhá v logaritmickém čase, což má za následek průměrný výkon případu o (log n).
Jaký je rozdíl mezi binárním vyhledáváním a lineárním vyhledáváním?
I když lineární i binární vyhledávání jsou metody 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 netříděných seznamech. Třídění seznamu má obecně průměrnou složitost n log n. lineární vyhledávání je jednoduché a přímočaré, než binární vyhledávání. Lineární vyhledávání je ale příliš pomalé na to, aby mohlo být použito s velkými seznamy, kvůli jeho průměrnému výkonu případu. 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í by však mohla být docela složitá a studie ukázala, že přesný kód pro binární vyhledávání lze najít pouze v pěti z dvaceti knih.
