Pausa caffè #156. Come utilizzare il metodo Arrays.binarySearch() in Java

Fonte: FreeCodeCamp Con questo articolo imparerai come utilizzare il metodo Arrays.binarySearch() in Java.

Cos'è Arrays.binarySearch() in Java?

La documentazione ufficiale per il metodo Arrays.binarySearch() afferma:

• Questo metodo cerca nella matrice di byte specificata il valore specificato utilizzando un algoritmo di ricerca binaria.
• L'array deve essere ordinato (utilizzando il metodo sort(byte[]) ) prima che venga effettuata la chiamata. Se non viene ordinato, i risultati non verranno determinati.
• Se l'array contiene più elementi con il valore specificato, non esiste alcuna garanzia su quale verrà trovato.

In termini semplici, il metodo Arrays.binarySearch() può cercare un dato elemento in un array ordinato e restituirne l'indice, se trovato.

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';

		int foundItemIndex = Arrays.binarySearch(vowels, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

Il metodo Arrays.binarySearch() accetta l'array che desideri cercare come primo argomento e la chiave che stai cercando come secondo argomento. L'output del programma sopra sarà: Ricorda che il metodo restituisce l'indice dell'elemento trovato, non l'elemento stesso. In questo modo puoi memorizzare l'indice come numero intero come quello utilizzato in questo esempio. Per impostazione predefinita, il metodo utilizza il primo indice dell'array come punto iniziale della ricerca e la lunghezza dell'array come punto finale della ricerca. In questo caso, l'indice iniziale è 0 e l'indice finale è 6. Invece di utilizzare gli indici iniziale e finale predefiniti, puoi definirli tu stesso. Ad esempio, se desideri cercare dall'indice 2 all'indice 4, potresti farlo in questo modo:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

In questo caso, il metodo Arrays.binarySearch() accetta l'array che si desidera cercare come primo argomento, l'indice iniziale come secondo argomento, l'indice finale come terzo e la chiave come quarto. Finché mantieni l'indice finale entro la lunghezza dell'array, il metodo dovrebbe funzionare correttamente. Ma se lo superi, otterrai un'eccezione dell'indice dell'array fuori range . È piuttosto semplice, vero? Il metodo restituisce l'indice dell'elemento se viene trovato. Ma cosa succede se non trova l'elemento indicato?

Cosa succede quando Arrays.binarySearch() non trova un determinato elemento?

Diamo un'altro sguardo alla documentazione ufficiale per il metodo Arrays.binarySearch() :

• Il metodo trova l'indice di una chiave nei risultati della ricerca se è contenuta nell'array entro l'intervallo specificato; altrimenti otteniamo (-(punto di inserimento) - 1) .
• Il punto di inserimento è definito come il punto in cui verrà inserita una chiave nell'array: l'indice del primo elemento dell'intervallo è maggiore della chiave, oppure toIndex (indice finale) se tutti gli elementi dell'intervallo sono inferiori al chiave specificata.
• Tieni presente che il valore restituito sarà maggiore o uguale a 0 solo quando viene trovata la chiave.

Non molto chiaro, vero? La prima riga afferma che il metodo restituirà l'indice della chiave dalla ricerca se viene trovata nell'array. Se non viene trovato, l'output sarà uguale al valore (-(punto di inserimento) - 1) . A seconda della chiave di ricerca, il punto di inserimento può avere significati diversi. Diciamo di avere un array [5, 6, 7, 8, 9, 10] e una chiave di ricerca pari a 0 , che chiaramente non è nell'array. In questo caso, la chiave di ricerca è inferiore a tutti gli elementi dell'array. Ma il primo elemento maggiore della chiave di ricerca è 5 . Pertanto, nel nostro caso il punto di inserimento sarà: Puoi implementarlo in uno snippet di codice come questo:

package arrays;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 0)); // -1
	}
}

Supponiamo ancora di avere un array [5, 6, 7, 8, 9, 10] e una chiave di ricerca pari a 12 , che chiaramente non è nell'array. In questo caso la chiave di ricerca è maggiore di tutti gli elementi dell'array. Qui il punto di inserimento sarà così: Ricorda che se non specifichi manualmente l'indice finale, il metodo utilizza la lunghezza dell'array come indice finale, che in questo caso è 6 . Puoi implementarlo in uno snippet di codice come questo:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 12)); // -7
	}
}

Tuttavia, i risultati cambieranno se definisci manualmente gli indici di inizio e fine:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		int startIndex = 1;
		int endIndex = 3;

		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2
		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4

	}
}

Prova a calcolare tu stesso i valori. Puoi anche utilizzare il metodo Arrays.binarySearch() con simboli come questo:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key));

	}
}

Gli stessi principi si applicano se la chiave di ricerca specificata non viene trovata. Ma quando si confronta un carattere nell'array con una determinata chiave di ricerca, verrà utilizzato il codice ASCII del carattere corrispondente. Cioè, A (65) sarà inferiore a a (97) . Tienilo in considerazione durante il controllo incrociato dell'output del tuo programma.