Kaffeepause Nr. 156. So verwenden Sie die Methode Arrays.binarySearch() in Java

Quelle: FreeCodeCamp In diesem Artikel erfahren Sie, wie Sie die Methode Arrays.binarySearch() in Java verwenden.

Was ist Arrays.binarySearch() in Java?

In der offiziellen Dokumentation zur Arrays.binarySearch()- Methode heißt es:

• Diese Methode durchsucht das angegebene Byte-Array mithilfe eines binären Suchalgorithmus nach dem angegebenen Wert.
• Das Array muss vor dem Aufruf sortiert werden (mit der Methode sort(byte[])). Wenn es nicht sortiert ist, werden die Ergebnisse nicht ermittelt.
• Wenn das Array mehrere Elemente mit dem angegebenen Wert enthält, gibt es keine Garantie, welches gefunden wird.

Einfach ausgedrückt kann die Methode Arrays.binarySearch() nach einem bestimmten Element in einem sortierten Array suchen und seinen Index zurückgeben, wenn er gefunden wird.

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);

	}
}

Die Methode Arrays.binarySearch() verwendet das zu durchsuchende Array als erstes Argument und den gesuchten Schlüssel als zweites Argument. Die Ausgabe des obigen Programms wird sein: Denken Sie daran, dass die Methode den Index des gefundenen Elements zurückgibt, nicht das Element selbst. Auf diese Weise können Sie den Index wie in diesem Beispiel als Ganzzahl speichern. Standardmäßig verwendet die Methode den ersten Index des Arrays als Startpunkt der Suche und die Länge des Arrays als Endpunkt der Suche. In diesem Fall ist der Startindex 0 und der Endindex 6. Anstatt den standardmäßigen Start- und Endindex zu verwenden, können Sie diese selbst definieren. Wenn Sie beispielsweise von Index 2 bis Index 4 suchen möchten, können Sie dies folgendermaßen tun:

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 diesem Fall verwendet die Methode Arrays.binarySearch() das zu durchsuchende Array als erstes Argument, den Startindex als zweites Argument, den Endindex als drittes und den Schlüssel als viertes. Solange Sie den Endindex innerhalb der Länge des Arrays halten, sollte die Methode einwandfrei funktionieren. Wenn Sie diesen jedoch überschreiten, erhalten Sie eine Ausnahme vom Typ „Array index out of range“ (Array-Index außerhalb des gültigen Bereichs) . Es ist ziemlich einfach, oder? Die Methode gibt den Index des Elements zurück, wenn es gefunden wird. Aber was passiert, wenn das angegebene Element nicht gefunden wird?

Was passiert, wenn Arrays.binarySearch() ein bestimmtes Element nicht findet?

Werfen wir noch einmal einen Blick auf die offizielle Dokumentation zur Arrays.binarySearch() -Methode :

• Die Methode findet den Index eines Schlüssels in den Suchergebnissen, wenn er im Array innerhalb des angegebenen Bereichs enthalten ist; andernfalls erhalten wir (-(Einfügepunkt) - 1) .
• Der Einfügepunkt ist als der Punkt definiert, an dem ein Schlüssel in das Array eingefügt wird: Der Index des ersten Elements im Bereich ist größer als der Schlüssel oder toIndex (Endindex), wenn alle Elemente im Bereich kleiner als der sind angegebenen Schlüssel.
• Beachten Sie, dass der Rückgabewert nur dann größer oder gleich 0 ist, wenn der Schlüssel gefunden wird.

Nicht ganz klar, oder? Die erste Zeile besagt, dass die Methode den Index des Schlüssels aus der Suche zurückgibt, wenn er im Array gefunden wird. Wenn es nicht gefunden wird, entspricht die Ausgabe dem Wert (-(Einfügepunkt) - 1) . Je nach Suchbegriff kann der Einfügepunkt unterschiedliche Bedeutungen haben. Nehmen wir an, wir haben ein Array [5, 6, 7, 8, 9, 10] und einen Suchschlüssel von 0 , der eindeutig nicht im Array enthalten ist. In diesem Fall ist der Suchschlüssel kleiner als alle Elemente des Arrays. Aber das erste Element, das größer als der Suchschlüssel ist, ist 5 . In unserem Fall lautet der Einfügepunkt also : Sie können dies in einem Code-Snippet wie diesem implementieren:

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
	}
}

Nehmen wir erneut an, dass wir ein Array [5, 6, 7, 8, 9, 10] und einen Suchschlüssel von 12 haben , der eindeutig nicht im Array enthalten ist. In diesem Fall ist der Suchschlüssel größer als alle Elemente des Arrays. Hier sieht der Einfügepunkt so aus: Denken Sie daran: Wenn Sie den Endindex nicht manuell angeben, verwendet die Methode die Länge des Arrays als Endindex, in diesem Fall 6 . Sie können dies in einem Code-Snippet wie diesem implementieren:

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
	}
}

Die Ergebnisse ändern sich jedoch, wenn Sie die Start- und Endindizes manuell definieren:

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

	}
}

Versuchen Sie, die Werte selbst zu berechnen. Sie können die Methode Arrays.binarySearch() auch mit Symbolen wie diesen verwenden:

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));

	}
}

Die gleichen Grundsätze gelten, wenn der angegebene Suchschlüssel nicht gefunden wird. Beim Vergleich zwischen einem Zeichen im Array und einem bestimmten Suchschlüssel wird jedoch der ASCII-Code des entsprechenden Zeichens verwendet. Das heißt, A (65) ist kleiner als a (97) . Berücksichtigen Sie dies, wenn Sie die Ausgabe Ihres Programms überprüfen.