logo

TechCodeview

Algoritmes de cerca

Algorismes de cerca són eines essencials en informàtica que s'utilitzen per localitzar elements específics dins d'una col·lecció de dades. Aquests algorismes estan dissenyats per navegar de manera eficient a través de les estructures de dades per trobar la informació desitjada, fent-los fonamentals en diverses aplicacions com ara bases de dades, cercadors web , i més.

Algorisme de cerca

Taula de contingut



guineu o llop

Què és la recerca?

La cerca és el procés fonamental de localitzar un element o element específic dins d'una col·lecció de dades . Aquesta recopilació de dades pot prendre diverses formes, com ara matrius, llistes, arbres o altres representacions estructurades. L'objectiu principal de la cerca és determinar si l'element desitjat existeix dins de les dades i, si és així, identificar-ne la ubicació precisa o recuperar-lo. Té un paper important en diverses tasques computacionals i aplicacions del món real, com ara la recuperació d'informació, l'anàlisi de dades, els processos de presa de decisions i molt més.

Cerca de terminologies:

Element objectiu:

En la cerca, sempre hi ha un element o element objectiu específic que voleu trobar dins de la recollida de dades. Aquest objectiu pot ser un valor, un registre, una clau o qualsevol altra entitat de dades d'interès.

dormir en js

Espai de cerca:

L'espai de cerca fa referència a tota la col·lecció de dades dins de la qual esteu buscant l'element objectiu. Depenent de l'estructura de dades utilitzada, l'espai de cerca pot variar en mida i organització.

Complexitat:

La cerca pot tenir diferents nivells de complexitat segons l'estructura de dades i l'algorisme utilitzat. La complexitat sovint es mesura en termes de requisits de temps i espai.

Determinista vs. no determinista:

Alguns algorismes de cerca, com ara cerca binària , són deterministes, és a dir, segueixen un enfocament clar i sistemàtic. D'altres, com la cerca lineal, no són deterministes, ja que poden necessitar examinar tot l'espai de cerca en el pitjor dels casos.

punt de primavera

Importància de cercar a DSA:

  • Eficiència: Els algorismes de cerca eficients milloren el rendiment del programa.
  • Recuperació de dades: Cerca i recupera ràpidament dades específiques de grans conjunts de dades.
  • Sistemes de bases de dades: Permet consultar ràpidament les bases de dades.
  • Solucionar problemes: S'utilitza en una àmplia gamma de tasques de resolució de problemes.

Aplicacions de cerca:

Els algorismes de cerca tenen nombroses aplicacions en diversos camps. Aquí hi ha algunes aplicacions habituals:

  • Recuperació d'informació: Els motors de cerca com Google, Bing i Yahoo utilitzen algorismes de cerca sofisticats per recuperar informació rellevant de grans quantitats de dades al web.
  • Sistemes de bases de dades: La cerca és fonamental en els sistemes de bases de dades per recuperar registres de dades específics basats en les consultes dels usuaris, millorant l'eficiència en la recuperació de dades.
  • Comerç electrònic: La cerca és crucial a les plataformes de comerç electrònic perquè els usuaris trobin productes ràpidament en funció de les seves preferències, especificacions o paraules clau.
  • Xarxa: En xarxes, s'utilitzen algorismes de cerca per encaminar paquets de manera eficient a través de xarxes, trobar camins òptims i gestionar recursos de xarxa.
  • Intel · ligència artificial: Els algorismes de cerca tenen un paper vital en les aplicacions d'IA, com ara la resolució de problemes, el joc (per exemple, els escacs) i els processos de presa de decisions.
  • Reconeixement de patró: Els algorismes de cerca s'utilitzen en tasques de concordança de patrons, com ara el reconeixement d'imatges, el reconeixement de veu i el reconeixement d'escriptura a mà.

Conceptes bàsics d'algorismes de cerca:

  • Introducció a la cerca - Tutorial d'estructura de dades i algorisme
  • Importància de la cerca a l'estructura de dades
  • Quin és l'objectiu de l'algorisme de cerca?

Algorismes de cerca:

  • Cerca lineal
  • Cerca lineal Sentinel
  • Cerca binària
  • Cerca meta binària | Cerca binària unilateral
  • Cerca ternaria
  • Salt de cerca
  • Cerca per interpolació
  • Cerca exponencial
  • Cerca de Fibonacci
  • La cerca binària omnipresent

Comparacions entre diferents algorismes de cerca:

  • Cerca lineal vs cerca binària
  • Cerca per interpolació vs cerca binària
  • Per què es prefereix la cerca binària a la cerca ternària?
  • La cerca lineal Sentinel és millor que la cerca lineal normal?

Implementacions de biblioteques d'algorismes de cerca:

  • Funcions de cerca binària en C++ STL (binary_search, lower_bound i upper_bound)
  • Arrays.binarySearch() a Java amb exemples | Set 1
  • Arrays.binarySearch() a Java amb exemples | Set 2 (Cerca al subbarray)
  • Collections.binarySearch() a Java amb exemples

Problemes fàcils de cercar:

  • Troba els tres elements més grans d'una matriu
  • Troba el número que falta
  • Trobeu el primer element que es repeteix en una matriu de nombres enters
  • Busca el nombre que falta i que es repeteix
  • Cerca, inseriu i suprimeix en una matriu ordenada
  • Compteu 1 en una matriu binària ordenada
  • Dos elements la suma dels quals és més propera a zero
  • Trobeu una parella amb la diferència donada
  • k elements més grans (o més petits) d'una matriu
  • Kè element més petit d'una matriu 2D ordenada per files i columnes
  • Troba elements comuns en tres matrius ordenades
  • Sostre en una matriu ordenada
  • Pis en una matriu ordenada
  • Trobeu l'element màxim d'una matriu que primer augmenta i després disminueix
  • Donada una matriu de mida n i un nombre k, troba tots els elements que apareixen més de n/k vegades

Problemes mitjans en la cerca:

  • Troba tots els triplets amb suma zero
  • Troba l'element abans del qual tots els elements són més petits que ell i després del qual tots són més grans
  • Trobeu la suma de parelles més gran en una matriu no ordenada
  • K'th element més petit/més gran de la matriu no ordenada
  • Cerca un element en una matriu ordenada i girada
  • Trobeu l'element mínim en una matriu ordenada i girada
  • Trobeu un element màxim
  • Màxim i mínim d'una matriu utilitzant el nombre mínim de comparacions
  • Trobeu un punt fix en una matriu donada
  • Troba les k paraules més freqüents d'un fitxer
  • Trobeu els k elements més propers a un valor donat
  • Donada una matriu ordenada i un nombre x, trobeu la parella de la matriu la suma del qual és més propera a x
  • Trobeu la parella més propera entre dues matrius ordenades
  • Trobeu els tres elements més propers a partir de tres matrius ordenades donades
  • Cerca binària de nombres racionals sense utilitzar l'aritmètica de coma flotant

Problemes difícils de cercar:

  • Mediana de dues matrius ordenades
  • Mediana de dues matrius ordenades de diferents mides
  • Cerca en una matriu gairebé ordenada
  • Troba la posició d'un element en una matriu ordenada de nombres infinits
  • Donada una matriu ordenada i rotada, cerqueu si hi ha una parella amb una suma determinada
  • K’th element més petit/més gran de la matriu no ordenada | Temps lineal en el pitjor dels casos
  • K’è element més gran d’un corrent
  • Millor primera cerca (cerca informada)

Links ràpids:

  • 'Problemes de pràctica' en la cerca
  • 'Quizzes' sobre cerca

Recomanat:

  • Apreneu l'estructura de dades i els algorismes | Tutorial DSA