Algoritmo di ricerca binaria in Java

1. Panoramica

In questo articolo, tratteremo i vantaggi di una ricerca binaria rispetto a una semplice ricerca lineare e illustreremo la sua implementazione in Java.

2. Necessità di una ricerca efficiente

Diciamo che siamo nel settore della vendita di vino e milioni di acquirenti visitano la nostra applicazione ogni giorno.

Attraverso la nostra app, un cliente può filtrare gli articoli che hanno un prezzo inferiore a n dollari, selezionare una bottiglia dai risultati della ricerca e aggiungerla al carrello. Abbiamo milioni di utenti che cercano vini con un limite di prezzo ogni secondo. I risultati devono essere rapidi.

Sul backend, il nostro algoritmo esegue una ricerca lineare attraverso l'intera lista dei vini confrontando il limite di prezzo inserito dal cliente con il prezzo di ogni bottiglia di vino in lista.

Quindi, restituisce gli articoli che hanno un prezzo inferiore o uguale al limite di prezzo. Questa ricerca lineare ha una complessità temporale di O (n) .

Ciò significa che maggiore è il numero di bottiglie di vino nel nostro sistema, più tempo ci vorrà. Il tempo di ricerca aumenta proporzionalmente al numero di nuovi articoli introdotti.

Se iniziamo a salvare gli elementi in ordine ordinato e cerchiamo gli elementi utilizzando la ricerca binaria, possiamo ottenere una complessità di O (log n) .

Con la ricerca binaria, il tempo impiegato dai risultati della ricerca aumenta naturalmente con la dimensione del set di dati, ma non proporzionalmente.

3. Ricerca binaria

In poche parole, l'algoritmo confronta il valore della chiave con l'elemento centrale dell'array; se sono diseguali, la metà di cui la chiave non può far parte viene eliminata e la ricerca continua per la metà rimanente fino a quando non riesce.

Ricorda: l'aspetto chiave qui è che l'array è già ordinato.

Se la ricerca termina con la metà rimanente vuota, la chiave non è nell'array.

3.1. Impl. Iterativo

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

Il metodo runBinarySearchIterately accetta un SortArray , una chiave e gli indici basso e alto di SortArray come argomenti. Quando il metodo esegue per la prima volta il low , il primo indice di SortArray, è 0, mentre il high , l'ultimo indice di SortArray, è uguale alla sua lunghezza - 1.

Il middle è l'indice centrale di SortArray . Ora l'algoritmo esegue un ciclo while confrontando la chiave con il valore dell'array dell'indice centrale di SortArray .

3.2. Impl. Ricorsivo

Ora, diamo un'occhiata anche a un'implementazione semplice e ricorsiva:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

Il metodo runBinarySearchRecursively accetta un SortArray , una chiave, gli indici basso e alto di SortArray .

3.3. Utilizzo di array. binarySearch ()

int index = Arrays.binarySearch(sortedArray, key); 

Un SortArray e una chiave int , da cercare nell'array di numeri interi, vengono passati come argomenti al metodo binarySearch della classe Java Arrays .

3.4. Utilizzo delle raccolte. binarySearch ()

int index = Collections.binarySearch(sortedList, key); 

Una SortList e una chiave Integer , che deve essere ricercata nell'elenco di oggetti Integer , vengono passati come argomenti al metodo binarySearch della classe Java Collections .

3.5. Prestazione

Se utilizzare un approccio ricorsivo o iterativo per scrivere l'algoritmo è principalmente una questione di preferenze personali. Ma ancora qui ci sono alcuni punti di cui dovremmo essere consapevoli:

1. La ricorsione può essere più lenta a causa dell'overhead di mantenere uno stack e di solito richiede più memoria

2. La ricorsione non è compatibile con lo stack . Può causare StackOverflowException durante l'elaborazione di set di dati di grandi dimensioni

3. La ricorsione aggiunge chiarezza al codice in quanto lo rende più breve rispetto all'approccio iterativo

Idealmente, una ricerca binaria eseguirà un numero inferiore di confronti rispetto a una ricerca lineare per valori grandi di n. Per valori minori di n, la ricerca lineare potrebbe funzionare meglio di una ricerca binaria.

Si dovrebbe sapere che questa analisi è teorica e potrebbe variare a seconda del contesto.

Inoltre, l'algoritmo di ricerca binaria necessita di un set di dati ordinato che abbia anche i suoi costi . Se usiamo un algoritmo di merge sort per ordinare i dati, al nostro codice viene aggiunta un'ulteriore complessità di n log n .

Quindi prima dobbiamo analizzare bene i nostri requisiti e poi prendere una decisione su quale algoritmo di ricerca si adatta meglio alle nostre esigenze.

4. Conclusione

Questo tutorial ha dimostrato l'implementazione di un algoritmo di ricerca binaria e uno scenario in cui sarebbe preferibile utilizzarlo invece di una ricerca lineare.

Si prega di trovare il codice per il tutorial su GitHub.