Articolo originale: https://www.freecodecamp.org/news/how-to-use-arrays-binarysearch-in-java/

In questo articolo, ti mostrerò come utilizzare il metodo Arrays.binarySearch() in Java.

Cos'è Arrays.binarySearch() in Java?

Secondo la documentazione ufficiale sul metodo Arrays.binarySearch():

Ricerca nell'array di byte specificato il valore indicato usando l'algoritmo di ricerca binaria.

L'array deve essere ordinato (ad esempio con il metodo sort(byte[])) prima della chiamata. Se non è ordinato, il risultato non è definito.

Se l'array contiene più elementi con il valore specificato, non è garantito quale di essi sarà trovato.

In parole povere, il metodo Arrays.binarySearch() può cercare un dato elemento in un array ordinato e restituire il suo indice se la ricerca ha successo.

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vocali[] = {'a', 'e', 'i', 'o', 'u'};
		
		char chiave = 'i';
		
		int trovaIndiceElemento = Arrays.binarySearch(vocali, chiave);
		
		System.out.println("La vocale indicata ha indice: " + trovaIndiceElemento);

	}
}

Il metodo Arrays.binarySearch() prende come primo argomento l'array su cui effettuare la ricerca e la chiave di ricerca come secondo argomento. L'output di questo programma sarà:

La vocale indicata ha indice: 2

Ricorda, il metodo restituisce l'indice dell'elemento trovato e non l'elemento stesso. Quindi puoi conservare l'indice in un intero come quello usato in questo esempio.

Come impostazione predefinita, il metodo usa il primo indice dell'array come punto di partenza della ricerca e la lunghezza dell'array come termine. Quindi in questo caso l'indice di partenza è 0 e quello di fine è 6.

Invece di usare gli indici predefiniti, puoi definirli tu stesso. Ad esempio, se vuoi svolgere la ricerca dall'indice 2 all'indice 4, puoi farlo in questo modo:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vocali[] = {'a', 'e', 'i', 'o', 'u'};
		
		char chiave = 'i';
		int indicePartenza = 2;
		int indiceFine = 4;
		
		int trovaIndiceElemento = Arrays.binarySearch(vocali, indicePartenza, indiceFine, chiave);
		
		System.out.println("La vocale indicata ha indice: " + trovaIndiceElemento);

	}
}

In questo caso, il metodo Arrays.binarySearch() prende l'array su cui vuoi effettuare la ricerca come primo argomento, l'indice di partenza come secondo argomento, l'indice finale come terzo argomento e la chiave di ricerca come quarto argomento.

Finché mantieni l'indice finale entro la lunghezza dell'array, il metodo dovrebbe funzionare senza problemi. Se usi un indice maggiore, otterrai l'eccezione Array index out of range.

Semplice, vero? Il metodo restituisce l'indice dell'elemento, se questo viene trovato. Ma cosa succede se non trova l'elemento indicato?

Cosa succede quando Arrays.binarySearch() non trova l'elemento dato?

Ancora, secondo la documentazione ufficiale sul metodo Arrays.binarySearch():

Il metodo restituisce l'indice della chiave di ricerca, se contenuto nell'array all'interno dell'intervallo specificato; altrimenti (-(insertion point) - 1).

"Insertion point" è definito come il punto in cui la chiave dovrebbe essere inserita nell'array: l'indice del primo elemento nell'intervallo maggiore della chiave, o toIndex (indice finale) se tutti gli elementi nell'intervallo sono minori della chiave specificata.

Nota che questo garantisce che il valore di ritorno sarà >= 0 se e solo se la chiave è trovata.

Non molto chiaro, vero? Provo a spiegare. La prima riga afferma che il metodo restituisce l'indice della chiave di ricerca se la chiave viene trovata nell'array.

Se non viene trovata, l'output sarà uguale al valore di (-(insertion point) - 1). Qui, in base alla chiave di ricerca, insertion point può avere diversi valori.

Ipotizziamo di avere l'array [5, 6, 7, 8, 9, 10] e la chiave di ricerca 0, che è chiaramente non presente nell'array. In questo caso, la chiave di ricerca è minore di tutti gli elementi dell'array. Ma il primo elemento maggiore della chiave di ricerca è 5, quindi in questo caso il valore di insertion point sarà: 

(-(indice del primo elemento maggiore della chiave) - 1) = (0 - 1) = -1

Possiamo verificarlo nello snippet di codice seguente:

package arrays;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {		
		int numeri[] = {5, 6, 7, 8, 9, 10};
		
		System.out.println(Arrays.binarySearch(numeri, 0)); // -1
	}
}

Di nuovo, ipotizziamo di avere l'array [5, 6, 7, 8, 9, 10] e la chiave di ricerca 12, chiaramente non presente nell'array. In questo caso, la chiave di ricerca è maggiore di tutti gli elementi dell'array e il valore di insertion point sarà:

(-(l'indice finale (-(6) - 1) = (-6 - 1) = -7

Ricorda, quando non definisci manualmente un indice finale, il metodo usa la lunghezza dell'array come indice finale, che in questo caso è 6.

Possiamo verificarlo nello snippet di codice seguente:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {		
		int numeri[] = {5, 6, 7, 8, 9, 10};
		
		System.out.println(Arrays.binarySearch(numeri, 12)); // -7
	}
}

Tuttavia, i risultati cambieranno se definisci gli indici di partenza e di fine manualmente, in questo modo:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numeri[] = {5, 6, 7, 8, 9, 10};
		
		int indicePartenza = 1;
		int indiceFine = 3;
		
		System.out.println(Arrays.binarySearch(numeri, indicePartenza, indiceFine, 5)); // -2
		System.out.println(Arrays.binarySearch(numeri, indicePartenza, indiceFine, 10)); // -4

	}
}

Prova tu stesso a calcolare i valori. Puoi anche usare il metodo Arrays.binarySearch() con dei caratteri, in questo modo:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vocali[] = {'a', 'e', 'i', 'o', 'u'};
		
		char chiave = 'i';
		int indicePartenza = 2;
		int indiceFine = 4;
		
		System.out.println(Arrays.binarySearch(vocali, indicePartenza, indiceFine, chiave));

	}
}

Lo stesso principio si applica in questo caso, quando la chiave di ricerca fornita non viene trovata. Ma per il confronto di un carattere nell'array e una data chiave di ricerca, sarà utilizzato il codice ASCII corrispondente al carattere. Quindi A (65) sarà minore di a (97). Tienilo a mente quando controlli gli output del tuo programma.

In conclusione

Questo era praticamente tutto per questo metodo. Spero che adesso tu sia in grado di capire come funziona Arrays.binarySearch().

Buona programmazione!