logo

TechCodeview

Algoritmo di ricerca binaria – Implementazione iterativa e ricorsiva

Ricerca binaria Algoritmo è un algoritmo di ricerca utilizzato in un array ordinato per dividendo ripetutamente l'intervallo di ricerca a metà . L'idea della ricerca binaria è quella di utilizzare l'informazione che l'array è ordinato e ridurre la complessità temporale a O(log N).

Ricerca binaria è un algoritmo di ricerca utilizzato per trovare la posizione di un valore target all'interno di a smistato vettore. Funziona dividendo ripetutamente l'intervallo di ricerca a metà finché non viene trovato il valore target o l'intervallo è vuoto. L'intervallo di ricerca viene dimezzato confrontando l'elemento di destinazione con il valore medio dello spazio di ricerca.

ops concetti in Java

Per applicare l'algoritmo di ricerca binaria:



  • La struttura dei dati deve essere ordinata.
  • L'accesso a qualsiasi elemento della struttura dati richiede tempo costante.

Algoritmo di ricerca binaria:

In questo algoritmo,

  • Dividi lo spazio di ricerca in due metà per trovare l'indice medio mid .

Trovare l'indice medio mid nell'algoritmo di ricerca binaria

  • Confronta l'elemento centrale dello spazio di ricerca con la chiave.
  • Se la chiave si trova nell'elemento centrale, il processo viene terminato.
  • Se la chiave non viene trovata nell'elemento centrale, scegli quale metà verrà utilizzata come spazio di ricerca successivo.
    • Se la chiave è più piccola dell'elemento centrale, per la ricerca successiva verrà utilizzato il lato sinistro.
    • Se la chiave è più grande dell'elemento centrale, per la ricerca successiva verrà utilizzato il lato destro.
  • Questo processo continua finché non viene trovata la chiave o finché lo spazio di ricerca totale non viene esaurito.

Come funziona l'algoritmo di ricerca binaria?

Per comprendere il funzionamento della ricerca binaria, considerare la seguente illustrazione:

Considera un array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , e il obiettivo = 23 .

Primo passo: Calcola la metà e confronta l'elemento medio con la chiave. Se la chiave è inferiore all'elemento centrale, spostati a sinistra e se è maggiore della metà, sposta lo spazio di ricerca a destra.

  • La chiave (ovvero 23) è maggiore dell'elemento centrale corrente (ovvero 16). Lo spazio di ricerca si sposta a destra.

Algoritmo di ricerca binaria: confronta la chiave con 16

  • La chiave è inferiore all'attuale metà 56. Lo spazio di ricerca si sposta a sinistra.

Algoritmo di ricerca binaria: confronta la chiave con 56

Secondo passo: Se la chiave corrisponde al valore dell'elemento centrale, l'elemento viene trovato e la ricerca viene interrotta.

Algoritmo di ricerca binaria: corrispondenze chiave con metà

Ricerca binaria pratica consigliata Provalo!

IL Algoritmo di ricerca binaria può essere implementato nei due modi seguenti

  • Algoritmo di ricerca binaria iterativa
  • Algoritmo di ricerca binaria ricorsiva

Di seguito sono riportati gli pseudocodici per gli approcci.

Algoritmo di ricerca binaria iterativa:

Qui utilizziamo un ciclo while per continuare il processo di confronto della chiave e di divisione dello spazio di ricerca in due metà.

Implementazione dell'algoritmo di ricerca binaria iterativa:

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
Giava 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
Pitone 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
Javascript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= basso) { medio = basso + Math.floor((alto - basso) / 2);    // Se l'elemento è presente al centro // stesso if (arr[mid] == x) return mid;    // Se l'elemento è più piccolo di mid, allora // può essere presente nel sottoarray sinistro solo se (arr[mid]> x) high = mid - 1;    // Altrimenti l'elemento può essere presente solo // nel sottoarray destro altrimenti low = mid + 1;  } // Arriviamo qui quando l'elemento non è // presente nell'array return -1; } arr =nuovo Array(2, 3, 4, 10, 40);  x = 10;  n = lunghezza arr.;  risultato = ricercabinaria(arr, x);   (risultato == -1) ? console.log('L'elemento non è presente nell'array'): console.log ('L'elemento è presente nell'indice ' + risultato);   // Questo codice è un contributo di simranarora5sos e rshuklabbb>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
Produzione 
Element is present at index 3>

Complessità temporale: O(logN)
Spazio ausiliario: O(1)

Algoritmo di ricerca binaria ricorsiva:

Crea una funzione ricorsiva e confronta la metà dello spazio di ricerca con la chiave. E in base al risultato, restituisci l'indice in cui si trova la chiave o chiama la funzione ricorsiva per lo spazio di ricerca successivo.

Implementazione dell'algoritmo di ricerca binaria ricorsiva:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= basso) { int medio = basso + (alto - basso) / 2;  // Se l'elemento è presente al centro // stesso if (arr[mid] == x) return mid;  // Se l'elemento è più piccolo di mid, allora // può essere presente solo nel sottoarray sinistro se (arr[mid]> x) return BinarySearch(arr, low, mid - 1, x);  // Altrimenti l'elemento può essere presente solo // nel sottoarray destro return BinarySearch(arr, mid + 1, high, x);  } } // Codice driver int main() { int arr[] = { 2, 3, 4, 10, 40 };  interrogazione intera = 10;  int n = dimensioneof(arr) / dimensioneof(arr[0]);  int risultato = BinarySearch(arr, 0, n - 1, query);  (risultato == -1) ? cout<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= basso) { int medio = basso + (alto - basso) / 2;  // Se l'elemento è presente al centro // stesso if (arr[mid] == x) return mid;  // Se l'elemento è più piccolo di mid, allora // può essere presente solo nel sottoarray sinistro se (arr[mid]> x) return BinarySearch(arr, low, mid - 1, x);  // Altrimenti l'elemento può essere presente solo // nel sottoarray destro return BinarySearch(arr, mid + 1, high, x);  } // Arriviamo qui quando l'elemento non è // presente nell'array return -1; } // Codice driver int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = dimensioneof(arr) / dimensioneof(arr[0]);  intero x = 10;  int risultato = ricercabinaria(arr, 0, n - 1, x);  (risultato == -1) ? printf('L'elemento non è presente nell'array'): printf('L'elemento è presente nell'indice %d', risultato);  restituire 0; }>
Giava 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= basso) { int medio = basso + (alto - basso) / 2;  // Se l'elemento è presente al // middle stesso if (arr[mid] == x) return mid;  // Se l'elemento è più piccolo di mid, allora // può essere presente solo nel sottoarray sinistro se (arr[mid]> x) return BinarySearch(arr, low, mid - 1, x);  // Altrimenti l'elemento può essere presente solo // nel sottoarray destro return BinarySearch(arr, mid + 1, high, x);  } // Raggiungiamo qui quando l'elemento non è presente // nell'array return -1;  } // Codice driver public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.lunghezza;  intero x = 10;  int risultato = ob.binarySearch(arr, 0, n - 1, x);  if (risultato == -1) System.out.println( 'L'elemento non è presente nell'array');  else System.out.println( 'L'elemento è presente nell'indice ' + risultato);  } } /* Questo codice è un contributo di Rajat Mishra */>
Pitone 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= basso: medio = basso + (alto - basso) // 2 # Se l'elemento è presente al centro stesso if arr[mid] == x: return mid # Se l'elemento è più piccolo di mid, allora # può essere presente solo nel sottoarray sinistro elif arr[mid]> x: return ricercabinaria(arr, low, mid-1, x) # Altrimenti l'elemento può essere presente solo # nel sottoarray destro else: return ricercabinaria(arr, mid + 1, high, x ) # L'elemento non è presente nell'array else: return -1 # Codice driver if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Risultato della chiamata di funzione = BinarySearch( arr, 0, len(arr)-1, x) if risultato != -1: print('L'elemento è presente nell'indice', risultato) else: print('L'elemento non è presente nell'array')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= basso) { int medio = basso + (alto - basso) / 2;  // Se l'elemento è presente al // middle stesso if (arr[mid] == x) return mid;  // Se l'elemento è più piccolo di mid, allora // può essere presente solo nel sottoarray sinistro se (arr[mid]> x) return BinarySearch(arr, low, mid - 1, x);  // Altrimenti l'elemento può essere presente solo // nel sottoarray destro return BinarySearch(arr, mid + 1, high, x);  } // Raggiungiamo qui quando l'elemento non è presente // nell'array return -1;  } // Codice driver public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Lunghezza;  intero x = 10;  int risultato = ricercabinaria(arr, 0, n - 1, x);  if (risultato == -1) Console.WriteLine( 'L'elemento non è presente nell'arrau');  else Console.WriteLine('Elemento presente nell'indice ' + risultato);  } } // Questo codice è fornito da Sam007.>
Javascript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= basso) { let mid = basso + Math.floor((alto - basso) / 2);  // Se l'elemento è presente al centro // stesso if (arr[mid] == x) return mid;  // Se l'elemento è più piccolo di mid, allora // può essere presente solo nel sottoarray sinistro se (arr[mid]> x) return BinarySearch(arr, low, mid - 1, x);  // Altrimenti l'elemento può essere presente solo // nel sottoarray destro return BinarySearch(arr, mid + 1, high, x);  } // Arriviamo qui quando l'elemento non è // presente nell'array return -1; } lascia arr = [ 2, 3, 4, 10, 40 ]; sia x = 10; let n = arr.length let result = BinarySearch(arr, 0, n - 1, x); (risultato == -1) ? console.log( 'L'elemento non è presente nell'array'): console.log('L'elemento è presente nell'indice ' +risultato);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $basso) { $medio = ceil($basso + ($alto - $basso) / 2); // Se l'elemento è presente // al centro stesso if ($arr[$mid] == $x) return floor($mid); // Se l'elemento è più piccolo di // mid, allora può essere // presente nel sottoarray sinistro solo se ($arr[$mid]> $x) return BinarySearch($arr, $low, $mid - 1, $x ); // Altrimenti l'elemento può // essere presente solo nel sottoarray destro return BinarySearch($arr, $mid + 1, $high, $x); } // Raggiungiamo qui quando l'elemento // non è presente nell'array return -1; } // Codice driver $arr = array(2, 3, 4, 10, 40); $n = conteggio($arr); $x = 10; $risultato = ricercabinaria($arr, 0, $n - 1, $x); if(($risultato == -1)) echo 'L'elemento non è presente nell'array'; else echo 'L'elemento è presente nell'indice ', $risultato; ?>>
Produzione 
Element is present at index 3>
  • Complessità temporale:
    • Caso migliore: O(1)
    • Caso medio: O(log N)
    • Caso peggiore: O(log N)
  • Spazio ausiliario: O(1), se si considera lo stack di chiamate ricorsivo, lo spazio ausiliario sarà O(logN).
  • La ricerca binaria può essere utilizzata come elemento costitutivo per algoritmi più complessi utilizzati nell'apprendimento automatico, come algoritmi per l'addestramento di reti neurali o per trovare gli iperparametri ottimali per un modello.
  • Può essere utilizzato per la ricerca nella grafica computerizzata come algoritmi per il ray tracing o la mappatura delle texture.
  • Può essere utilizzato per la ricerca in un database.
  • La ricerca binaria è più veloce della ricerca lineare, soprattutto per array di grandi dimensioni.
  • Più efficiente di altri algoritmi di ricerca con una complessità temporale simile, come la ricerca per interpolazione o la ricerca esponenziale.
  • La ricerca binaria è particolarmente adatta per la ricerca di set di dati di grandi dimensioni archiviati nella memoria esterna, ad esempio su un disco rigido o nel cloud.
  • L'array dovrebbe essere ordinato.
  • La ricerca binaria richiede che la struttura dati da cercare sia archiviata in posizioni di memoria contigue.
  • La ricerca binaria richiede che gli elementi dell'array siano comparabili, ovvero che possano essere ordinati.

Domande frequenti (FAQ) sulla ricerca binaria:

1. Cos'è la ricerca binaria?

La ricerca binaria è un algoritmo efficiente per trovare un valore di destinazione all'interno di un array ordinato. Funziona dividendo ripetutamente l'intervallo di ricerca a metà.

2. Come funziona la ricerca binaria?

La ricerca binaria confronta il valore di destinazione con l'elemento centrale dell'array. Se sono uguali, la ricerca ha esito positivo. Se l'obiettivo è inferiore all'elemento centrale, la ricerca continua nella metà inferiore dell'array. Se l'obiettivo è maggiore, la ricerca continua nella metà superiore. Questo processo si ripete finché non viene trovata la destinazione o l'intervallo di ricerca è vuoto.

3. Qual è la complessità temporale della ricerca binaria?

La complessità temporale della ricerca binaria è O(log2n), dove n è il numero di elementi nell'array. Questo perché la dimensione dell'intervallo di ricerca viene dimezzata in ogni passaggio.

4. Quali sono i prerequisiti per la ricerca binaria?

La ricerca binaria richiede che l'array sia ordinato in ordine crescente o decrescente. Se l'array non è ordinato, non possiamo utilizzare la ricerca binaria per cercare un elemento nell'array.

5. Cosa succede se l'array non è ordinato per la ricerca binaria?

Se l'array non è ordinato, la ricerca binaria potrebbe restituire risultati errati. Si basa sulla natura ordinata dell'array per prendere decisioni su quale metà dell'array cercare.

6. È possibile applicare la ricerca binaria a dati non numerici?

Sì, la ricerca binaria può essere applicata a dati non numerici purché esista un ordine definito per gli elementi. Può essere utilizzato, ad esempio, per cercare stringhe in ordine alfabetico.

7. Quali sono alcuni svantaggi comuni della ricerca binaria?

Lo svantaggio della ricerca binaria è che l'array di input deve essere ordinato per decidere in quale metà può trovarsi l'elemento di destinazione. Pertanto, per gli array non ordinati, è necessario ordinare l'array prima di applicare la ricerca binaria.

numero di 'Eulero' in Java'

8. Quando dovrebbe essere utilizzata la ricerca binaria?

La ricerca binaria dovrebbe essere utilizzata quando si cerca un valore di destinazione in un array ordinato, soprattutto quando la dimensione dell'array è grande. È particolarmente efficiente per set di dati di grandi dimensioni rispetto agli algoritmi di ricerca lineare.

9. La ricerca binaria può essere implementata in modo ricorsivo?

Sì, la ricerca binaria può essere implementata sia in modo iterativo che ricorsivo. L'implementazione ricorsiva spesso porta a un codice più conciso ma potrebbe avere un sovraccarico leggermente maggiore a causa dello spazio dello stack ricorsivo o delle chiamate di funzione.

10. La ricerca binaria è sempre la scelta migliore per effettuare ricerche in un array ordinato?

Sebbene la ricerca binaria sia molto efficiente per la ricerca in array ordinati, potrebbero esserci casi specifici in cui altri algoritmi di ricerca sono più appropriati, ad esempio quando si ha a che fare con set di dati di piccole dimensioni o quando l'array viene modificato frequentemente.

Articoli Correlati:

  • Ricerca binaria su risposta Tutorial con problemi
  • Ricerca lineare e ricerca binaria
  • Come identificare e risolvere i problemi di ricerca binaria?