La ricerca lineare in Java è sempre stata il metodo di riferimento per trovare un elemento in un array. Cerca ogni elemento dell'array in sequenza ed è estremamente facile da implementare. Tuttavia, i limiti della ricerca lineare sono evidenti quando l'array in questione contiene decine di migliaia di elementi. In tali casi, il metodo "divide et impera" implementato dalla ricerca binaria è molto più efficiente e preferibile per i programmatori che hanno in mente la complessità del tempo e dello spazio.
Ricerca binaria
Nella ricerca binaria, un array viene ripetutamente diviso in due metà finché non viene trovata la chiave (l'elemento che viene cercato). La divisione è virtuale, cioè l'integrità dei dati viene mantenuta. Ad ogni iterazione, viene focalizzato il valore medio dell'array. Se il valore è uguale alla chiave che stiamo cercando, il ciclo o la funzione ricorsiva termina. Altrimenti, continua a girare. Se il valore medio è maggiore della chiave, la funzione si concentra sulla prima metà dell'array e viceversa. Questo processo viene ripetuto finché non viene trovata la chiave o l'intero array è stato iterato.
Differenza tra ricerca lineare e binaria
Ricerca lineare |
Ricerca binaria |
Cerca in sequenza l'array |
Divide l'array in due metà finché non viene trovato il valore |
Funziona con qualsiasi matrice |
Funziona solo con array ordinati |
La complessità è O(N) |
La complessità è O(log2N) |
Può funzionare su array ordinati e non ordinati |
Può essere implementato solo su array ordinati. |
Meno complesso da implementare |
Più complesso da implementare |
Algoritmo di ricerca binaria
L'algoritmo della ricerca binaria è riportato di seguito.
- Determina il primo e l'ultimo punto della matrice. I punti verranno regolati ad ogni iterazione secondo l'array e la chiave da cercare.
- Scorri l'array e confronta il valore medio tra il primo e l'ultimo punto corrente. Nella prima iterazione, la prima e l'ultima variabile saranno le stesse di quelle effettive nell'array.
- Se la chiave è maggiore del valore medio, l'indice di tale valore verrà memorizzato nella nuova variabile "First".
- Se la chiave è inferiore al valore medio, l'indice di tale valore verrà memorizzato nella variabile "Last".
- Questa condizione viene ripetuta fino a quando una delle due condizioni diventa vera:
- Chiave trovata.
- L'intero array è stato iterato.
Di seguito viene fornito il codice per la ricerca binaria iterativa e la ricerca binaria ricorsiva.
Ricerca binaria iterativa
Di seguito è riportato il codice per la ricerca binaria con un metodo iterativo.
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
//Representing the Start and End Index After Division of Array
int start = 0;
int end = arr.length;
//Loop to Iterate Through the Array
for(int i = 0; iarr[n]){
start = n;
}
//If number to search for is greater than the arr value at index 'n'
else{
end = n;
}
}
//If number isn't found, return -1
return -1;
}
}
Ricerca binaria ricorsiva
Di seguito viene fornito il codice per Binary che utilizza la ricorsione.
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
//Base Case to Exit the Recursive Function
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
//If number is found at mean index of start and end
if(arr[n]==num)
return n;
//If number to search for is greater than the arr value at index 'n'
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
//If number to search for is greater than the arr value at index 'n'
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
Complessità temporale
Ad ogni iterazione che passa, l'array, ovvero lo spazio di ricerca, viene diviso a metà. Dopo ogni iterazione 'm', lo spazio di ricerca cambierà in una dimensione di N/2m. Nel peggiore dei casi, rimarremo solo con un elemento su un lato estremo dell'array. A questo punto, la complessità della ricerca binaria sarà k = log2N. La complessità temporale della ricerca lineare è O(N), il che fa sì che la ricerca binaria sia molto più veloce con la complessità O(log2N). Questo è il vantaggio principale dell'utilizzo della ricerca binaria rispetto alla ricerca lineare.
Complessità spaziale
La ricerca binaria utilizza tre diverse variabili: inizio, fine e metà. Queste tre variabili vengono create come puntatori che puntano alla posizione di memoria degli indici dell'array. Per questo motivo, la ricerca binaria è estremamente efficiente con lo spazio. La complessità spaziale della ricerca binaria iterativa è O(1). Per l'implementazione ricorsiva, è O(log N).
GO TO FULL VERSION