Rozdíl mezi binárním a lineárním vyhledáváním

Binární vyhledávání vs lineární vyhledávání

Lineární vyhledávání, také známé 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žitá k nalezení zadané hodnoty v seřazeném seznamu. Metoda binárního vyhledávání snižuje na polovinu počet kontrolovaných prvků (v každé iteraci), čímž se 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 určený prvek. Vstupem do metody lineárního vyhledávání je sekvence (například pole, kolekce nebo řetězec) a položka, kterou je třeba prohledat. Výstup je pravdivý, pokud je zadaná položka v rámci poskytnuté posloupnosti nebo nepravda, pokud není v posloupnosti. Protože tato metoda kontroluje každou položku v seznamu, dokud se nenajde určená 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é, než aby bylo použito při hledání prvků ve velkých seznamech. Ale to je velmi jednoduché a snáze implementovatelné.

Co je to binární vyhledávání?

Binární vyhledávání je také metoda používaná k nalezení určité položky v seřazeném seznamu. Tato metoda začíná porovnáním prohledávaného prvku s prvky uprostřed seznamu. Pokud porovnání zjistí, že oba prvky jsou stejné, metoda se zastaví a vrací polohu prvku. Pokud je hledaný prvek větší než prostřední, spustí metodu znovu pomocí pouze spodní poloviny seřazeného seznamu. Pokud je hledaný prvek menší než prostřední, spustí metodu znovu pomocí pouze horní poloviny seřazeného seznamu. Pokud hledaný prvek není v seznamu, metoda vrátí jedinečnou hodnotu, která to naznačuje. Metoda binárního vyhledávání proto snižuje počet porovnávaných prvků na polovinu (v každé iteraci) v závislosti na výsledku srovnání. V důsledku toho binární vyhledávání běží v logaritmickém čase, což má za následek průměrný výkon případu (log n).

Jaký je rozdíl mezi binárním a lineárním vyhledáváním??

I když lineární vyhledávání i binární vyhledávání jsou způsoby vyhledávání, mají několik rozdílů. Zatímco binární vyhledávání pracuje na seřazených seznamech, může liniové vyhledávání pracovat také na netříděných seznamech. Třídění seznamu má obecně složitost n log n. lineární vyhledávání je jednoduché a přímé provedení než binární vyhledávání. Lineární vyhledávání je však příliš pomalé na to, aby mohlo být použito ve velkých seznamech kvůli jeho průměrnému výkonu o (n). Na druhé straně je binární vyhledávání považováno za účinnější metodu, kterou lze použít u velkých seznamů. Realizace 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 nalézt pouze v pěti z dvaceti knih.