logo

TechCodeview

Algoritmy vyhľadávania

Vyhľadávacie algoritmy sú základnými nástrojmi v informatike, ktoré sa používajú na vyhľadávanie konkrétnych položiek v súbore údajov. Tieto algoritmy sú navrhnuté tak, aby efektívne prechádzali dátovými štruktúrami s cieľom nájsť požadované informácie, čo ich robí základnými v rôznych aplikáciách, ako napr. databázy, webové vyhľadávače , a viac.

Algoritmus vyhľadávania

Obsah



Čo je vyhľadávanie?

Hľadanie je základným procesom lokalizácia konkrétneho prvku alebo položky v rámci kolekcie údajov . Táto zbierka údajov môže mať rôzne formy, ako sú polia, zoznamy, stromy alebo iné štruktúrované reprezentácie. Primárnym cieľom vyhľadávania je určiť, či požadovaný prvok v údajoch existuje, a ak áno, identifikovať jeho presnú polohu alebo ho získať. Hrá dôležitú úlohu v rôznych výpočtových úlohách a aplikáciách v reálnom svete, vrátane vyhľadávania informácií, analýzy údajov, rozhodovacích procesov a ďalších.

Hľadanie terminológie:

Cieľový prvok:

Pri vyhľadávaní vždy existuje konkrétny cieľový prvok alebo položka, ktorú chcete nájsť v rámci kolekcie údajov. Týmto cieľom môže byť hodnota, záznam, kľúč alebo akákoľvek iná entita údajov, ktorá vás zaujíma.

Vyhľadávací priestor:

Vyhľadávací priestor sa vzťahuje na celú kolekciu údajov, v rámci ktorej hľadáte cieľový prvok. V závislosti od použitej štruktúry údajov sa môže vyhľadávací priestor líšiť veľkosťou a organizáciou.

zložitosť:

Vyhľadávanie môže mať rôzne úrovne zložitosti v závislosti od štruktúry údajov a použitého algoritmu. Zložitosť sa často meria z hľadiska časových a priestorových požiadaviek.

Deterministické vs. nedeterministické:

Niektoré vyhľadávacie algoritmy, napr binárne vyhľadávanie , sú deterministické, čo znamená, že sledujú jasný, systematický prístup. Iné, ako napríklad lineárne vyhľadávanie, sú nedeterministické, pretože v najhoršom prípade môžu potrebovať preskúmať celý priestor vyhľadávania.

Dôležitosť vyhľadávania v DSA:

  • Účinnosť: Výkon programu zlepšujú efektívne vyhľadávacie algoritmy.
  • Získavanie údajov: Rýchlo vyhľadajte a získajte špecifické údaje z veľkých súborov údajov.
  • Databázové systémy: Umožňuje rýchle vyhľadávanie v databázach.
  • Riešenie problémov: Používa sa v širokej škále úloh na riešenie problémov.

Aplikácie vyhľadávania:

Vyhľadávacie algoritmy majú množstvo aplikácií v rôznych oblastiach. Tu sú niektoré bežné aplikácie:

  • Získavanie informácií: Vyhľadávače ako Google, Bing a Yahoo používajú sofistikované vyhľadávacie algoritmy na získavanie relevantných informácií z obrovského množstva údajov na webe.
  • Databázové systémy: Vyhľadávanie je v databázových systémoch základom pre získavanie špecifických dátových záznamov na základe užívateľských dopytov, čím sa zvyšuje efektivita pri získavaní dát.
  • Elektronický obchod: Vyhľadávanie je v platformách elektronického obchodu kľúčové, aby používatelia rýchlo našli produkty na základe svojich preferencií, špecifikácií alebo kľúčových slov.
  • Networking: V sieti sa vyhľadávacie algoritmy používajú na efektívne smerovanie paketov cez siete, hľadanie optimálnych ciest a správu sieťových zdrojov.
  • Umela inteligencia: Vyhľadávacie algoritmy hrajú dôležitú úlohu v aplikáciách AI, ako je riešenie problémov, hranie hier (napr. šach) a rozhodovacie procesy.
  • Rozpoznávanie vzorov: Vyhľadávacie algoritmy sa používajú pri úlohách zhody vzorov, ako je rozpoznávanie obrázkov, rozpoznávanie reči a rozpoznávanie rukopisu.

Základy vyhľadávacích algoritmov:

  • Úvod do vyhľadávania – Príručka o štruktúre údajov a algoritmoch
  • Význam vyhľadávania v dátovej štruktúre
  • Aký je účel vyhľadávacieho algoritmu?

Algoritmy vyhľadávania:

  • Lineárne vyhľadávanie
  • Sentinel Linear Search
  • Binárne vyhľadávanie
  • Meta binárne vyhľadávanie | Jednostranné binárne vyhľadávanie
  • Ternárne vyhľadávanie
  • Prejsť na vyhľadávanie
  • Vyhľadávanie interpolácie
  • Exponenciálne vyhľadávanie
  • Fibonacciho vyhľadávanie
  • Všadeprítomné binárne vyhľadávanie

Porovnania medzi rôznymi vyhľadávacími algoritmami:

  • Lineárne vyhľadávanie vs binárne vyhľadávanie
  • Interpolačné vyhľadávanie vs binárne vyhľadávanie
  • Prečo je binárne vyhľadávanie uprednostňované pred ternárnym vyhľadávaním?
  • Je Sentinel Linear Search lepšie ako normálne lineárne vyhľadávanie?

Knižničné implementácie vyhľadávacích algoritmov:

Jednoduché problémy s vyhľadávaním:

  • Nájdite najväčšie tri prvky v poli
  • Nájdite chýbajúce číslo
  • Nájdite prvý opakujúci sa prvok v poli celých čísel
  • Nájdite chýbajúce a opakujúce sa číslo
  • Vyhľadajte, vložte a odstráňte v zoradenom poli
  • Počítajte 1 v zoradenom binárnom poli
  • Dva prvky, ktorých súčet je najbližšie k nule
  • Nájdite pár s daným rozdielom
  • k najväčších (alebo najmenších) prvkov v poli
  • K-tý najmenší prvok v 2D poli zoradenom po riadkoch a stĺpcoch
  • Nájdite spoločné prvky v troch zoradených poliach
  • Strop v triedenom poli
  • Podlaha v triedenom poli
  • Nájdite maximálny prvok v poli, ktorý sa najprv zvyšuje a potom klesá
  • Dané pole s veľkosťou n a číslom k nájdite všetky prvky, ktoré sa vyskytujú viac ako n/k-krát

Stredné problémy s vyhľadávaním:

  • Nájdite všetky trojice s nulovým súčtom
  • Nájdite prvok, pred ktorým sú všetky prvky menšie ako on a po ktorom sú všetky väčšie
  • Nájdite najväčší súčet párov v nezoradenom poli
  • K’th najmenší/najväčší prvok v netriedenom poli
  • Vyhľadajte prvok v zoradenom a otočenom poli
  • Nájdite minimálny prvok v zoradenom a otočenom poli
  • Nájdite vrcholový prvok
  • Maximum a minimum poľa pomocou minimálneho počtu porovnaní
  • Nájdite pevný bod v danom poli
  • Nájdite k najčastejších slov zo súboru
  • Nájdite k prvkov najbližších k danej hodnote
  • Vzhľadom na zoradené pole a číslo x nájdite v poli dvojicu, ktorej súčet je najbližšie k x
  • Nájdite najbližší pár z dvoch zoradených polí
  • Nájdite tri najbližšie prvky z daných troch zoradených polí
  • Binárne vyhľadávanie racionálnych čísel bez použitia aritmetiky s pohyblivou rádovou čiarkou

Ťažké problémy s vyhľadávaním:

  • Medián dvoch triedených polí
  • Medián dvoch triedených polí rôznych veľkostí
  • Hľadajte v takmer zoradenom poli
  • Nájdite polohu prvku v zoradenom poli nekonečných čísel
  • Vzhľadom na zoradené a otočené pole zistite, či existuje pár s daným súčtom
  • K’th najmenší/najväčší prvok v netriedenom poli | V najhoršom prípade Lineárny čas
  • K’th najväčší prvok v prúde
  • Najlepšie prvé vyhľadávanie (informované vyhľadávanie)

Rýchle odkazy:

  • „Problémy s cvičením“ pri vyhľadávaní
  • „Kvízy“ o vyhľadávaní

Odporúčané:

  • Naučte sa dátovú štruktúru a algoritmy | Príručka DSA