logo

TechCodeview

Algoritmy vyhledávání

Vyhledávací algoritmy jsou základními nástroji v informatice používané k vyhledání konkrétních položek ve sbírce dat. Tyto algoritmy jsou navrženy tak, aby efektivně procházely datovými strukturami a nacházely požadované informace, což je činí zásadními v různých aplikacích, jako je např. databáze, webové vyhledávače , a více.

Algoritmus hledání

tostring java metoda

Obsah



Co je vyhledávání?

Hledání je základním procesem umístění určitého prvku nebo položky v rámci kolekce dat . Tato sbírka dat může mít různé formy, jako jsou pole, seznamy, stromy nebo jiné strukturované reprezentace. Primárním cílem vyhledávání je určit, zda požadovaný prvek v datech existuje, a pokud ano, identifikovat jeho přesnou polohu nebo jej získat. Hraje důležitou roli v různých výpočetních úlohách a aplikacích v reálném světě, včetně vyhledávání informací, analýzy dat, rozhodovacích procesů a dalších.

Hledání terminologie:

Cílový prvek:

Při vyhledávání vždy existuje konkrétní cílový prvek nebo položka, kterou chcete v kolekci dat najít. Tímto cílem může být hodnota, záznam, klíč nebo jakákoli jiná zájmová datová entita.

Vyhledat prostor:

Vyhledávací prostor odkazuje na celou kolekci dat, ve které hledáte cílový prvek. V závislosti na použité datové struktuře se může vyhledávací prostor lišit velikostí a organizací.

Složitost:

Vyhledávání může mít různé úrovně složitosti v závislosti na struktuře dat a použitém algoritmu. Složitost se často měří z hlediska požadavků na čas a prostor.

řetězec tokenizer java

Deterministické vs. nedeterministické:

Nějaké vyhledávací algoritmy, např binární vyhledávání , jsou deterministické, což znamená, že sledují jasný, systematický přístup. Jiné, jako je lineární vyhledávání, jsou nedeterministické, protože v nejhorším případě mohou potřebovat prozkoumat celý vyhledávací prostor.

Význam vyhledávání v DSA:

  • Účinnost: Výkon programu zlepšují efektivní vyhledávací algoritmy.
  • Načítání dat: Rychle vyhledejte a načtěte konkrétní data z velkých datových sad.
  • Databázové systémy: Umožňuje rychlé dotazování databází.
  • Řešení problému: Používá se v široké škále úloh při řešení problémů.

Aplikace vyhledávání:

Vyhledávací algoritmy mají mnoho aplikací v různých oblastech. Zde jsou některé běžné aplikace:

  • Získávání informací: Vyhledávače jako Google, Bing a Yahoo používají sofistikované vyhledávací algoritmy k získávání relevantních informací z obrovského množství dat na webu.
  • Databázové systémy: Vyhledávání je v databázových systémech zásadní pro získávání specifických datových záznamů na základě uživatelských dotazů, což zvyšuje efektivitu při získávání dat.
  • Elektronický obchod: Vyhledávání je na platformách elektronického obchodu klíčové, aby uživatelé rychle našli produkty na základě svých preferencí, specifikací nebo klíčových slov.
  • Networking: V sítích se vyhledávací algoritmy používají pro efektivní směrování paketů v sítích, hledání optimálních cest a správu síťových zdrojů.
  • Umělá inteligence: Vyhledávací algoritmy hrají zásadní roli v aplikacích AI, jako je řešení problémů, hraní her (např. šachy) a rozhodovací procesy.
  • Rozpoznávání vzorů: Vyhledávací algoritmy se používají v úlohách porovnávání vzorů, jako je rozpoznávání obrázků, rozpoznávání řeči a rozpoznávání rukopisu.

Základy vyhledávacích algoritmů:

  • Úvod do vyhledávání – Výukový program pro datovou strukturu a algoritmus
  • Význam vyhledávání v datové struktuře
  • Jaký je účel vyhledávacího algoritmu?

Algoritmy vyhledávání:

  • Lineární vyhledávání
  • Sentinel Linear Search
  • Binární vyhledávání
  • Meta binární vyhledávání | Jednostranné binární vyhledávání
  • Ternární vyhledávání
  • Skokové vyhledávání
  • Hledání interpolace
  • Exponenciální vyhledávání
  • Fibonacciho vyhledávání
  • Všudypřítomné binární vyhledávání

Srovnání mezi různými vyhledávacími algoritmy:

  • Lineární vyhledávání vs binární vyhledávání
  • Interpolační vyhledávání vs binární vyhledávání
  • Proč je binární vyhledávání upřednostňováno před ternárním vyhledáváním?
  • Je Sentinel Linear Search lepší než normální lineární vyhledávání?

Knihovní implementace vyhledávacích algoritmů:

  • Funkce binárního vyhledávání v C++ STL (binary_search, lower_bound a upper_bound)
  • Arrays.binarySearch() v Javě s příklady | Sada 1
  • Arrays.binarySearch() v Javě s příklady | Sada 2 (Hledat v dílčím poli)
  • Collections.binarySearch() v Javě s příklady

Snadné problémy s hledáním:

  • Najděte největší tři prvky v poli
  • Najděte chybějící číslo
  • Najděte první opakující se prvek v poli celých čísel
  • Najděte chybějící a opakující se číslo
  • Vyhledávání, vkládání a mazání v seřazeném poli
  • Počítejte jedničky v seřazeném binárním poli
  • Dva prvky, jejichž součet je nejbližší nule
  • Najděte dvojici s daným rozdílem
  • k největších (nebo nejmenších) prvků v poli
  • K-tý nejmenší prvek v 2D poli uspořádaném po řádcích a sloupcích
  • Najděte společné prvky ve třech seřazených polích
  • Strop v seřazeném poli
  • Podlaha v tříděném poli
  • Najděte maximální prvek v poli, které se nejprve zvětšuje a poté snižuje
  • Zadané pole o velikosti n a čísle k najděte všechny prvky, které se vyskytují více než n/kkrát

Střední problémy s hledáním:

  • Najděte všechny trojice s nulovým součtem
  • Najděte prvek, před kterým jsou všechny prvky menší než on, a po kterém jsou všechny větší
  • Najděte největší párový součet v netříděném poli
  • K’th nejmenší/největší prvek v netříděném poli
  • Vyhledejte prvek v seřazeném a otočeném poli
  • Najděte minimální prvek v seřazeném a otočeném poli
  • Najděte vrcholový prvek
  • Maximum a minimum pole pomocí minimálního počtu porovnání
  • Najděte pevný bod v daném poli
  • Najděte k nejfrekventovanějších slov ze souboru
  • Najděte k prvků nejbližších dané hodnotě
  • Vzhledem k seřazenému poli a číslu x najděte v poli dvojici, jejíž součet je nejbližší x
  • Najděte nejbližší pár ze dvou seřazených polí
  • Najděte tři nejbližší prvky z daných tří seřazených polí
  • Binární hledání racionálních čísel bez použití aritmetiky s pohyblivou řádovou čárkou

Těžké problémy s hledáním:

  • Medián dvou seřazených polí
  • Medián dvou seřazených polí různých velikostí
  • Hledejte v téměř seřazeném poli
  • Najděte pozici prvku v seřazeném poli nekonečných čísel
  • Vzhledem k seřazenému a otočenému poli zjistěte, zda existuje pár s daným součtem
  • K’th nejmenší/největší prvek v netříděném poli | V nejhorším případě lineární čas
  • K’th největší prvek v proudu
  • Nejlepší první vyhledávání (informované vyhledávání)

Rychlé odkazy:

  • „Problémy procvičování“ při hledání
  • „Kvízy“ o vyhledávání

Doporučeno:

  • Naučte se datovou strukturu a algoritmy | Výukový program DSA