logo

TechCodeview

Algoritmi de căutare

Algoritmi de căutare sunt instrumente esențiale în informatică utilizate pentru a localiza elemente specifice într-o colecție de date. Acești algoritmi sunt proiectați pentru a naviga eficient prin structurile de date pentru a găsi informațiile dorite, făcându-le fundamentale în diverse aplicații, cum ar fi baze de date, motoare de căutare web , și altele.

Algoritm de căutare

Cuprins



Ce este căutarea?

Căutarea este procesul fundamental al localizarea unui anumit element sau element într-o colecție de date . Această colecție de date poate lua diferite forme, cum ar fi matrice, liste, arbori sau alte reprezentări structurate. Obiectivul principal al căutării este de a determina dacă elementul dorit există în date și, dacă da, de a identifica locația exactă a acestuia sau de a-l recupera. Joacă un rol important în diverse sarcini de calcul și aplicații din lumea reală, inclusiv regăsirea informațiilor, analiza datelor, procesele de luare a deciziilor și multe altele.

Căutarea terminologiei:

Element țintă:

În căutare, există întotdeauna un anumit element țintă sau element pe care doriți să-l găsiți în colectarea de date. Această țintă poate fi o valoare, o înregistrare, o cheie sau orice altă entitate de date de interes.

Spațiu de căutare:

Spațiul de căutare se referă la întreaga colecție de date în care căutați elementul țintă. În funcție de structura datelor utilizată, spațiul de căutare poate varia ca dimensiune și organizare.

Complexitate:

Căutarea poate avea diferite niveluri de complexitate în funcție de structura datelor și de algoritmul utilizat. Complexitatea este adesea măsurată în termeni de cerințe de timp și spațiu.

Determinist versus non-determinist:

Unii algoritmi de căutare, cum ar fi căutare binară , sunt deterministe, adică urmează o abordare clară, sistematică. Altele, cum ar fi căutarea liniară, sunt nedeterministe, deoarece ar putea fi nevoie să examineze întregul spațiu de căutare în cel mai rău caz.

Importanța căutării în DSA:

  • Eficienţă: Algoritmii eficienți de căutare îmbunătățesc performanța programului.
  • Recuperare de date: Găsiți și preluați rapid date specifice din seturi mari de date.
  • Sisteme de baze de date: Permite interogarea rapidă a bazelor de date.
  • Rezolvarea problemelor: Folosit într-o gamă largă de sarcini de rezolvare a problemelor.

Aplicații de căutare:

Algoritmii de căutare au numeroase aplicații în diverse domenii. Iată câteva aplicații comune:

  • Găsirea informațiilor: Motoarele de căutare precum Google, Bing și Yahoo folosesc algoritmi de căutare sofisticați pentru a prelua informații relevante din cantități mari de date de pe web.
  • Sisteme de baze de date: Căutarea este fundamentală în sistemele de baze de date pentru preluarea înregistrărilor de date specifice pe baza interogărilor utilizatorilor, îmbunătățind eficiența în regăsirea datelor.
  • Comerț electronic: Căutarea este crucială în platformele de comerț electronic pentru ca utilizatorii să găsească rapid produse pe baza preferințelor, specificațiilor sau cuvintelor cheie.
  • Rețele: În rețele, algoritmii de căutare sunt utilizați pentru rutarea eficientă a pachetelor prin rețele, găsirea căilor optime și gestionarea resurselor rețelei.
  • Inteligenţă artificială: Algoritmii de căutare joacă un rol vital în aplicațiile AI, cum ar fi rezolvarea problemelor, jocul (de exemplu, șah) și procesele de luare a deciziilor
  • Recunoasterea formelor: Algoritmii de căutare sunt utilizați în sarcinile de potrivire a modelelor, cum ar fi recunoașterea imaginilor, recunoașterea vorbirii și recunoașterea scrisului de mână.

Elementele de bază ale algoritmilor de căutare:

  • Introducere în Căutare – Structura datelor și Tutorial algoritm
  • Importanța căutării în Structura datelor
  • Care este scopul algoritmului de căutare?

Algoritmi de căutare:

  • Căutare liniară
  • Căutare liniară sentinelă
  • Căutare binară
  • Căutare meta binară | Căutare binară unilaterală
  • Căutare ternară
  • Salt de căutare
  • Căutare prin interpolare
  • Căutare exponențială
  • Căutare Fibonacci
  • Căutarea binară omniprezentă

Comparații între diferiți algoritmi de căutare:

  • Căutare liniară vs căutare binară
  • Căutare prin interpolare vs căutare binară
  • De ce este preferată Căutarea binară față de Căutarea ternară?
  • Căutarea liniară Sentinel este mai bună decât căutarea liniară normală?

Implementări în bibliotecă ale algoritmilor de căutare:

  • Funcții de căutare binară în C++ STL (binary_search, lower_bound și upper_bound)
  • Arrays.binarySearch() în Java cu exemple | Setul 1
  • Arrays.binarySearch() în Java cu exemple | Setul 2 (Căutare în subbaraj)
  • Collections.binarySearch() în Java cu exemple

Probleme ușoare la căutare:

  • Găsiți cele mai mari trei elemente dintr-o matrice
  • Găsiți numărul lipsă
  • Găsiți primul element care se repetă dintr-o matrice de numere întregi
  • Găsiți numărul care lipsește și care se repetă
  • Căutați, inserați și ștergeți într-o matrice sortată
  • Numărați 1 într-un tablou binar sortat
  • Două elemente a căror sumă este cea mai apropiată de zero
  • Găsiți o pereche cu diferența dată
  • k cele mai mari (sau cele mai mici) elemente dintr-o matrice
  • Cel mai mic element K dintr-o matrice 2D sortată pe rând și pe coloană
  • Găsiți elemente comune în trei matrice sortate
  • Tavan într-o matrice sortată
  • Podea într-o matrice sortată
  • Găsiți elementul maxim dintr-o matrice care mai întâi crește și apoi descrește
  • Având în vedere o matrice de mărimea n și un număr k, găsiți toate elementele care apar de mai mult de n/k ori

Probleme medii la căutare:

  • Găsiți toate tripletele cu sumă zero
  • Găsiți elementul înaintea căruia toate elementele sunt mai mici decât acesta și după care toate sunt mai mari
  • Găsiți cea mai mare sumă de perechi dintr-o matrice nesortată
  • Cel mai mic/cel mai mare element K’ din matricea nesortată
  • Căutați un element într-o matrice sortată și rotită
  • Găsiți elementul minim într-o matrice sortată și rotită
  • Găsiți un element de vârf
  • Maximul și minimul unei matrice folosind numărul minim de comparații
  • Găsiți un punct fix într-o matrice dată
  • Găsiți cele mai frecvente k cuvinte dintr-un fișier
  • Găsiți k elemente cele mai apropiate de o valoare dată
  • Având în vedere o matrice sortată și un număr x, găsiți perechea din matrice a cărei sumă este cea mai apropiată de x
  • Găsiți cea mai apropiată pereche din două tablouri sortate
  • Găsiți trei elemente cele mai apropiate din trei tablouri sortate date
  • Căutare binară pentru numere raționale fără a utiliza aritmetica în virgulă mobilă

Probleme grele la căutare:

  • Mediana a două matrice sortate
  • Mediana a două matrice sortate de dimensiuni diferite
  • Căutați într-o matrice aproape sortată
  • Găsiți poziția unui element într-o matrice sortată de numere infinite
  • Având în vedere o matrice sortată și rotită, găsiți dacă există o pereche cu o sumă dată
  • Cel mai mic/cel mai mare element K’ din matricea nesortată | Cel mai rău caz Linear Time
  • K-ul cel mai mare element dintr-un flux
  • Cea mai bună prima căutare (căutare informată)

Link-uri rapide:

  • „Probleme de practică” la căutare
  • „Chestionare” despre căutare

Recomandat:

  • Aflați structura datelor și algoritmi | Tutorial DSA