Struttura dei dati e algoritmi di ricerca binaria

La ricerca binaria è un algoritmo di ricerca veloce con complessità di runtime di Ο (log n). Questo algoritmo di ricerca funziona sul principio del divide et impera. Affinché questo algoritmo funzioni correttamente, la raccolta dei dati dovrebbe essere nella forma ordinata.

La ricerca binaria cerca un elemento particolare confrontando l'elemento più centrale della raccolta. Se si verifica una corrispondenza, viene restituito l'indice dell'elemento. Se l'elemento centrale è maggiore dell'elemento, l'elemento viene cercato nel sotto-array a sinistra dell'elemento centrale. In caso contrario, l'elemento viene cercato nel sotto-array a destra dell'elemento centrale. Questo processo continua anche sul sottoarray finché la dimensione del sottoarray non si riduce a zero.

Come funziona la ricerca binaria?

Affinché una ricerca binaria funzioni, è obbligatorio ordinare l'array di destinazione. Impareremo il processo di ricerca binaria con un esempio pittorico. Quello che segue è il nostro array ordinato e supponiamo di dover cercare la posizione del valore 31 utilizzando la ricerca binaria.

Per prima cosa, determineremo metà dell'array usando questa formula:

mid = low + (high - low) / 2

Eccolo, 0 + (9-0) / 2 = 4 (valore intero di 4,5). Quindi, 4 è la metà della matrice.

Ora confrontiamo il valore memorizzato nella posizione 4, con il valore cercato, ad esempio 31. Troviamo che il valore nella posizione 4 è 27, che non è una corrispondenza. Poiché il valore è maggiore di 27 e abbiamo un array ordinato, sappiamo anche che il valore di destinazione deve essere nella parte superiore dell'array.

Modifichiamo il nostro valore medio + 1 e troviamo di nuovo il nuovo valore medio.

low = mid + 1
mid = low + (high - low) / 2

La nostra nuova metà ora ha 7 anni. Confrontiamo il valore memorizzato nella posizione 7 con il nostro valore target 31.

Il valore memorizzato nella posizione 7 non è una corrispondenza, piuttosto è più di quello che stiamo cercando. Quindi, il valore deve essere nella parte inferiore di questa posizione.

Quindi, calcoliamo di nuovo la metà. Questa volta sono le 5.

Confrontiamo il valore memorizzato nella posizione 5 con il nostro valore target. Scopriamo che è una corrispondenza.

Concludiamo che il valore target 31 è memorizzato nella posizione 5.

La ricerca binaria dimezza gli elementi ricercabili e quindi riduce il conteggio dei confronti da effettuare a numeri molto inferiori.

Pseudocodice

Lo pseudocodice degli algoritmi di ricerca binaria dovrebbe essere simile a questo:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Per conoscere l'implementazione della ricerca binaria utilizzando array nel linguaggio di programmazione C, fare clic qui .