Ricerca lineare vs ricerca binaria: differenza tra ricerca lineare e ricerca binaria

Pubblicato: 2021-02-09

Sommario

introduzione

L'allocazione di memoria contigua nei linguaggi di programmazione fornisce un'implementazione flessibile per la memorizzazione di più punti dati. Questo può essere utilizzato al suo apice se vogliamo separare i dati e unire tutti i dati simili in una struttura di dati contigua come un array, un elenco, ecc.

L'allocazione di memoria contigua ha molte implementazioni in applicazioni del mondo reale come un sistema operativo in computer, sistemi di gestione di database, ecc. Questa struttura dati è considerata flessibile perché l'aggiunta di un nuovo punto dati a un array richiede solo una singola unità di tempo, ad esempio; O(1).

Ma il problema sorge quando vogliamo guardare una voce particolare o cercare una voce particolare perché tutte le applicazioni del mondo reale si basano sui comandi di accesso ai dati. E questo compito deve essere abbastanza veloce da soddisfare la velocità del processore e della memoria.

Esistono vari algoritmi di ricerca divisi in base al numero di confronti che facciamo per cercare l'elemento.

Se confrontiamo ogni punto dati nell'array per cercare un elemento, viene considerato come una ricerca sequenziale. Ma se stiamo confrontando solo pochi elementi saltando alcuni dei confronti, allora viene considerata come una ricerca a intervalli. Ma abbiamo bisogno che un array sia in ordine (crescente o decrescente) per eseguire una ricerca a intervalli su di esso.

La complessità temporale della ricerca sequenziale è lineare O(n) e la complessità temporale della ricerca binaria (un esempio di ricerca a intervalli) è O(log n). Inoltre, ci sono altri algoritmi di ricerca come la ricerca esponenziale, la ricerca per salto, ecc.

Ma vengono utilizzate principalmente la ricerca lineare e la ricerca binaria, dove la ricerca lineare è per dati casuali o non ordinati e la ricerca binaria è per dati ordinati e ordinati. L'hashing è uno speciale algoritmo di ricerca in cui la complessità temporale dell'accesso a un punto dati è O(1).

Esaminiamo prima gli algoritmi della ricerca lineare e della ricerca binaria e quindi confrontiamo le differenze tra la ricerca lineare e la ricerca binaria.

Ricerca lineare

Come già discusso, l'algoritmo di ricerca lineare confronta ogni elemento nell'array, ed ecco il codice per farlo.

classe pubblica UpGrad {
 public static int linear_search ( int [] arr, int n, int k){
 for ( int i= 0 ; i<n; i++)
 se (arr[i]==k)
 ritorno i+ 1 ;
 ritorno – 1 ;
 }
 public static void main (String[] args){
 int [] arr= nuovo int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
 int k= 13 ;
 int n=arr.lunghezza;
 int r=ricerca_lineare(arr, n, k);
 se (r==- 1 )
 System.out.println( “elemento non trovato” );
 altro
 System.out.println( “elemento trovato nella posizione “ +r+ ”” );
 }
 }

Esaminiamo il codice.

Abbiamo dichiarato una funzione linear_search, che prevede un array, una chiave intera come parametri. Ora dobbiamo scorrere tutti gli elementi e confrontare se corrisponde alla nostra chiave di ricerca, quindi abbiamo scritto un ciclo for che scorre sull'array e al suo interno c'è un ciclo if che controlla se il numero in quella posizione corrisponde con la chiave di ricerca o meno. Se troviamo una corrispondenza, restituiremo la posizione. Se non c'è un tale elemento nell'array, restituiremo -1 alla fine della funzione.

Nota che se abbiamo più apparizioni dello stesso numero, restituiremo la posizione della sua prima occorrenza.

Venendo al metodo principale, abbiamo dichiarato e inizializzato un array intero. Quindi stiamo inizializzando la chiave che deve essere ricercata. Qui stiamo codificando l'array e la chiave, ma puoi cambiarlo in input dell'utente. Ora che abbiamo l'elenco degli elementi e la chiave da cercare, viene chiamato il metodo di ricerca lineare e viene annotato l'indice restituito. Successivamente controlliamo il valore restituito e stampiamo l'indice se la chiave esiste, altrimenti la chiave di stampa non è stata trovata.

Ricerca binaria

La ricerca binaria è più ottimizzata della ricerca lineare, ma l'array deve essere ordinato per applicare la ricerca binaria. Ed ecco il codice per farlo.

classe pubblica UpGrad {
 public static int binary_search ( int [] arr, int k){
 int l= 0 ,h=arr.lunghezza- 1 ,mid= 0 ;
 mentre (l<=h){
 medio=l+(hl)/ 2 ;
 se (arr[mid]==k)
 ritorno metà+ 1 ;
 altrimenti se (arr[mid]>k)
 h=metà- 1 ;
 altro
 l=metà+ 1 ;
 }
 ritorno – 1 ;
 }
 public static void main (String[] args){
 int [] arr= nuovo int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
 int k= 8 ;
 int r=ricerca_binaria(arr,k);
 se (r==- 1 )
 System.out.println( “elemento non trovato” );
 altro
 System.out.println( “elemento trovato nella posizione “ +r+ ”” );
 }
 }

Esaminiamo il codice.

Abbiamo dichiarato un metodo binary_search che prevede un array intero ordinato e una chiave intera come parametri. Stiamo inizializzando le variabili basso, alto, medio. Qui basso, alto sono i puntatori in cui basso sarà all'indice 0 e alto sarà all'indice n all'inizio. Quindi, come funziona la ricerca binaria?

Per prima cosa, calcoleremo la metà di basso e alto. Possiamo calcolare il medio come (basso+alto)/2, ma a volte alto potrebbe essere un numero elevato e l'aggiunta di basso a alto può portare a un overflow di numeri interi. Quindi calcolare il medio come basso+(alto-basso)/2 sarebbe un modo ottimale.

Confronteremo l'elemento a metà con la chiave di ricerca e restituiremo l'indice se troviamo una corrispondenza. Altrimenti verificheremo se l'elemento centrale è maggiore della chiave o minore della chiave. Se la metà è maggiore, dobbiamo controllare solo la prima metà dell'array perché tutti gli elementi nella seconda metà dell'array sono maggiori della chiave, quindi aggiorneremo l'alto a metà-1.

Allo stesso modo, se mid è minore di chiave, allora dobbiamo cercare nella seconda metà dell'array, aggiornando quindi il basso a medio+1. Ricorda che la ricerca binaria si basa sull'algoritmo di diminuzione e conquista poiché stiamo ignorando una delle metà dell'array in ogni iterazione.

Tornando al nostro codice, abbiamo costruito il metodo principale. Inizializza una matrice ordinata e una chiave di ricerca, effettua una chiamata alla ricerca binaria e stampa i risultati.

Ora che abbiamo esaminato gli algoritmi sia della ricerca lineare che della ricerca binaria, confrontiamo entrambi gli algoritmi.

Ricerca lineare e ricerca binaria

Lavorando

  • La ricerca lineare scorre tutti gli elementi e li confronta con la chiave da cercare.
  • La ricerca binaria riduce saggiamente la dimensione dell'array che deve essere ricercato e confronta ogni volta la chiave con l'elemento centrale.

Struttura dati

  • La ricerca lineare è flessibile con tutte le strutture di dati come un array, un elenco, un elenco collegato, ecc.
  • La ricerca binaria non può essere eseguita su tutte le strutture di dati poiché è necessario l'attraversamento multidirezionale. Pertanto non è possibile utilizzare strutture di dati come l'elenco collegato singolo.

Prerequisiti

  • La ricerca lineare può essere eseguita su tutti i tipi di dati, i dati possono essere casuali o ordinati l'algoritmo rimane lo stesso. Quindi non c'è bisogno di alcun pre-lavoro da fare.
  • La ricerca binaria funziona solo su un array ordinato. Quindi l'ordinamento di un array è un prerequisito per questo algoritmo.

Caso d'uso

  • La ricerca lineare è generalmente preferita per set di dati più piccoli e ordinati casualmente.
  • La ricerca binaria è preferita per set di dati relativamente più grandi e ordinati.

Efficacia

  • La ricerca lineare è meno efficiente nel caso di set di dati più grandi.
  • La ricerca binaria è più efficiente nel caso di set di dati più grandi.

Complessità temporale

  • Nella ricerca lineare, la complessità del caso migliore è O(1) dove l'elemento si trova al primo indice. La complessità del caso peggiore è O(n) dove l'elemento si trova all'ultimo indice o l'elemento non è presente nell'array.
  • Nella ricerca binaria, la complessità del caso migliore è O(1) dove l'elemento si trova all'indice centrale. La complessità del caso peggiore è O( log 2 n).

Funzionamento a secco

Supponiamo di avere un array di dimensione 10.000.

  • In una ricerca lineare, la complessità del caso migliore è O(1) e la complessità del caso peggiore è O(10000).
  • In una ricerca binaria, la complessità del caso migliore è O(1) e la complessità del caso peggiore è O( log 2 10000)=O(13.287).

Conclusione

Abbiamo compreso l'importanza dell'accesso ai dati negli array, compreso gli algoritmi della ricerca lineare e della ricerca binaria. Ho esaminato i codici della ricerca lineare e della ricerca binaria. Confrontando le differenze tra la ricerca lineare e la ricerca binaria, è stato eseguito un test per un esempio di grandi dimensioni.

Ora che sei a conoscenza delle differenze tra ricerca lineare e ricerca binaria, prova a eseguire entrambi i codici per un set di dati di grandi dimensioni e confronta il tempo di esecuzione, inizia a esplorare diversi algoritmi di ricerca e prova a implementarli!

Se sei curioso di conoscere la scienza dei dati, dai un'occhiata al Diploma PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1- on-1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.

Impara i corsi di scienza dei dati online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.

Confronta la ricerca lineare e la ricerca binaria utilizzando le loro complessità.

La ricerca binaria è più ottimizzata ed efficiente della ricerca lineare in molti modi, specialmente quando gli elementi sono in ordine. Il motivo si riduce alla complessità di entrambe le ricerche.
Ricerca lineare
1. Complessità temporale: O(N) - Poiché nella ricerca lineare, attraversiamo l'array per verificare se qualche elemento corrisponde alla chiave. Nel peggiore dei casi, l'elemento sarà presente alla fine dell'array, quindi dobbiamo attraversare la fine, e quindi la complessità temporale sarà O(N) dove N è il numero totale di elementi dell'array.
2. Complessità spaziale: O(1) - Non stiamo usando alcuno spazio aggiuntivo, quindi la complessità dello spazio sarà O(1).
Ricerca binaria
1. Complessità temporale: O(log N) - Nella ricerca binaria, la ricerca si riduce della metà poiché dobbiamo solo guardare fino al centro dell'array. E stiamo costantemente abbreviando la nostra ricerca al centro della sezione in cui l'elemento è presente.
2. Complessità spaziale: O(1)
- Non stiamo utilizzando spazio aggiuntivo, quindi la complessità dello spazio sarà O(1).

Esiste un altro metodo per cercare un elemento in un array?

Sebbene la ricerca lineare e la ricerca binaria siano spesso utilizzate per la ricerca, esiste in effetti un altro metodo di ricerca: il metodo di interpolazione. È una versione ottimizzata di Binary Search in cui tutti gli elementi sono distribuiti uniformemente.
L'idea alla base di questo metodo è che nella ricerca binaria, guardiamo sempre al centro dell'array. Ma con questo metodo, la ricerca può andare in posizioni diverse a seconda di dove si trova la chiave. Ad esempio, se la chiave si trova vicino all'ultimo elemento dell'array, la ricerca inizierà dalla fine dell'array.

Quali sono le diverse complessità temporali della ricerca per interpolazione?

La complessità temporale della ricerca di interpolazione nel caso peggiore è O(N) poiché nel caso peggiore, la chiave sarà alla fine dell'array, quindi l'iteratore deve attraversare l'array.
La complessità media del caso sarà O(log(log N) poiché l'elemento può essere ovunque nell'array. Potrebbe anche essere vicino al punto di partenza.
La complessità del caso migliore sarà O(1) poiché, nel migliore dei casi, la chiave sarà il primo elemento dell'array.