Iskalni algoritmi so bistvena orodja v računalništvu, ki se uporabljajo za iskanje določenih elementov v zbirki podatkov. Ti algoritmi so zasnovani za učinkovito krmarjenje po podatkovnih strukturah za iskanje želenih informacij, zaradi česar so temeljni v različnih aplikacijah, kot je npr. baze podatkov, spletni iskalniki , in več.

Algoritem iskanja

java array dynamic

Kazalo

• Kaj je iskanje?
• Iskanje terminologije
• Pomen iskanja v DSA
• Aplikacije iskanja
• Osnove iskalnih algoritmov
• Iskalni algoritmi
• Primerjave med različnimi algoritmi iskanja
• Izvedbe iskalnih algoritmov v knjižnici
• Enostavne težave pri iskanju
• Srednje težave pri iskanju
• Težke težave pri iskanju

Kaj je iskanje?

Iskanje je temeljni proces iskanje določenega elementa ali predmeta znotraj zbirke podatkov . Ta zbirka podatkov ima lahko različne oblike, kot so nizi, seznami, drevesa ali druge strukturirane predstavitve. Primarni cilj iskanja je ugotoviti, ali želeni element obstaja v podatkih, in če obstaja, ugotoviti njegovo natančno lokacijo ali ga pridobiti. Ima pomembno vlogo pri različnih računalniških nalogah in aplikacijah v realnem svetu, vključno s pridobivanjem informacij, analizo podatkov, procesi odločanja in več.

pomladne st

Iskanje terminologij:

Ciljni element:

Pri iskanju vedno obstaja določen ciljni element ali predmet, ki ga želite najti v zbirki podatkov. Ta cilj je lahko vrednost, zapis, ključ ali katera koli druga podatkovna entiteta, ki vas zanima.

Iskanje prostora:

Iskalni prostor se nanaša na celotno zbirko podatkov, znotraj katere iščete ciljni element. Odvisno od uporabljene strukture podatkov se lahko iskalni prostor razlikuje po velikosti in organizaciji.

Kompleksnost:

Iskanje ima lahko različne stopnje kompleksnosti, odvisno od strukture podatkov in uporabljenega algoritma. Kompleksnost se pogosto meri glede na potrebe po času in prostoru.

Deterministični proti nedeterminističnim:

Nekaj ​​iskalnih algoritmov, npr binarno iskanje , so deterministični, kar pomeni, da sledijo jasnemu, sistematičnemu pristopu. Druge, kot je linearno iskanje, so nedeterministične, saj bodo v najslabšem primeru morda morale pregledati celoten iskalni prostor.

krepko besedilo css

Pomen iskanja v DSA:

• Učinkovitost: Učinkoviti iskalni algoritmi izboljšajo delovanje programa.
• Pridobivanje podatkov: Hitro poiščite in pridobite določene podatke iz velikih naborov podatkov.
• Sistemi baz podatkov: Omogoča hitro poizvedovanje po bazah podatkov.
• Reševanje problema: Uporablja se pri številnih nalogah reševanja problemov.

Aplikacije iskanja:

Iskalni algoritmi imajo številne aplikacije na različnih področjih. Tukaj je nekaj pogostih aplikacij:

• Pridobivanje informacij: Iskalniki, kot so Google, Bing in Yahoo, uporabljajo sofisticirane algoritme iskanja za pridobivanje ustreznih informacij iz ogromnih količin podatkov na spletu.
• Sistemi baz podatkov: Iskanje je temeljnega pomena v sistemih baz podatkov za pridobivanje določenih podatkovnih zapisov na podlagi uporabniških poizvedb, kar izboljšuje učinkovitost pri pridobivanju podatkov.
• E-trgovina: Iskanje je v platformah e-trgovine ključnega pomena, da lahko uporabniki hitro najdejo izdelke na podlagi svojih preferenc, specifikacij ali ključnih besed.
• Omrežje: V omrežju se iskalni algoritmi uporabljajo za učinkovito usmerjanje paketov skozi omrežja, iskanje optimalnih poti in upravljanje omrežnih virov.
• Umetna inteligenca: Iskalni algoritmi igrajo ključno vlogo v aplikacijah AI, kot so reševanje problemov, igranje iger (npr. šaha) in procesi odločanja
• Prepoznavanje vzorcev: Iskalni algoritmi se uporabljajo pri nalogah ujemanja vzorcev, kot so prepoznavanje slik, prepoznavanje govora in prepoznavanje rokopisa.

Osnove iskalnih algoritmov:

• Uvod v iskanje – Vadnica za strukturo podatkov in algoritme
• Pomen iskanja v podatkovni strukturi
• Kaj je namen iskalnega algoritma?

Algoritmi iskanja:

• Linearno iskanje
• Sentinel linearno iskanje
• Binarno iskanje
• Meta binarno iskanje | Enostransko binarno iskanje
• Trojno iskanje
• Skoči iskanje
• Interpolacijsko iskanje
• Eksponentno iskanje
• Fibonaccijevo iskanje
• Vseprisotno binarno iskanje

Primerjave med različnimi algoritmi iskanja:

• Linearno iskanje proti binarnemu iskanju
• Interpolacijsko iskanje proti binarnemu iskanju
• Zakaj je binarno iskanje prednost pred ternarnim iskanjem?
• Ali je linearno iskanje Sentinel boljše od običajnega linearnega iskanja?

Izvedbe iskalnih algoritmov v knjižnici:

• Funkcije binarnega iskanja v C++ STL (binary_search, lower_bound in upper_bound)
• Arrays.binarySearch() v Javi s primeri | Komplet 1
• Arrays.binarySearch() v Javi s primeri | 2. niz (iskanje v podmatriki)
• Collections.binarySearch() v Javi s primeri

Enostavne težave pri iskanju:

• Poiščite največje tri elemente v nizu
• Poišči manjkajočo številko
• Poiščite prvi ponavljajoči se element v nizu celih števil
• Poišči manjkajoče in ponavljajoče se število
• Iskanje, vstavljanje in brisanje v razvrščeni matriki
• Štetje 1 v razvrščeni binarni matriki
• Dva elementa, katerih vsota je najbližja ničli
• Poišči par z dano razliko
• k največjih (ali najmanjših) elementov v matriki
• K-ti najmanjši element v 2D-matriki, razvrščeni po vrsticah in stolpcih
• Poiščite skupne elemente v treh razvrščenih nizih
• Strop v razvrščenem nizu
• Tla v razvrščenem nizu
• Poiščite največji element v nizu, ki najprej narašča in nato pada
• Podano je polje velikosti n in število k, poiščite vse elemente, ki se pojavijo več kot n/k-krat

Srednje težave pri iskanju:

• Poišči vse trojčke z vsoto nič
• Poišči element, pred katerim so vsi elementi manjši od njega in za katerim so vsi večji
• Poiščite največjo vsoto parov v nerazvrščenem nizu
• K’th najmanjši/največji element v nerazvrščenem nizu
• Poiščite element v razvrščeni in zasukani matriki
• Poiščite najmanjši element v razvrščeni in zasukani matriki
• Poiščite element vrha
• Največ in najmanj matrike z uporabo najmanjšega števila primerjav
• Poiščite fiksno točko v danem nizu
• Poiščite k najpogostejših besed iz datoteke
• Poiščite k najbližjih elementov dani vrednosti
• Glede na razvrščeno matriko in število x poiščite par v matriki, katerega vsota je najbližja x
• Poiščite najbližji par iz dveh razvrščenih nizov
• Poiščite tri najbližje elemente iz danih treh razvrščenih nizov
• Binarno iskanje racionalnih števil brez uporabe aritmetike s plavajočo vejico

Težke težave pri iskanju:

• Mediana dveh razvrščenih nizov
• Mediana dveh razvrščenih nizov različnih velikosti
• Iskanje v skoraj razvrščeni matriki
• Poiščite položaj elementa v razvrščenem nizu neskončnih števil
• Glede na razvrščeno in zasukano matriko poiščite, ali obstaja par z dano vsoto
• K’th najmanjši/največji element v nerazvrščenem nizu | Najslabši primer linearnega časa
• K-ti največji element v toku
• Najboljše prvo iskanje (Informirano iskanje)

Hitre povezave:

• 'Težave za vadbo' pri iskanju
• 'Kvizi' o iskanju

Priporočeno:

• Naučite se podatkovne strukture in algoritmov | Vadnica DSA