Przerwa kawowa #156. Jak używać metody Arrays.binarySearch() w Javie

Źródło: FreeCodeCamp W tym artykule dowiesz się, jak używać metody Arrays.binarySearch() w Javie.

Co to jest Arrays.binarySearch() w Javie?

Oficjalna dokumentacja metody Arrays.binarySearch() stwierdza:

• Ta metoda przeszukuje określoną tablicę bajtów pod kątem określonej wartości przy użyciu algorytmu wyszukiwania binarnego.
• Tablicę należy posortować (przy użyciu metody sort(byte[]) ) przed wykonaniem wywołania. Jeżeli nie zostanie ona posortowana, wyniki nie zostaną ustalone.
• Jeśli tablica zawiera wiele elementów o określonej wartości, nie ma gwarancji, który z nich zostanie znaleziony.

Mówiąc prościej, metoda Arrays.binarySearch() może wyszukiwać dany element w posortowanej tablicy i zwracać jego indeks, jeśli zostanie znaleziony.

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

	}
}

Metoda Arrays.binarySearch() jako pierwszy argument przyjmuje tablicę, którą chcesz przeszukać, a jako drugi argument szukany klucz. Wynikiem powyższego programu będzie: Pamiętaj, że metoda zwraca indeks znalezionego elementu, a nie sam element. W ten sposób możesz zapisać indeks jako liczbę całkowitą, taką jak ta użyta w tym przykładzie. Domyślnie metoda wykorzystuje pierwszy indeks tablicy jako punkt początkowy wyszukiwania, a długość tablicy jako punkt końcowy wyszukiwania. W tym przypadku indeks początkowy wynosi 0, a indeks końcowy wynosi 6. Zamiast korzystać z domyślnego indeksu początkowego i końcowego, możesz je zdefiniować samodzielnie. Na przykład, jeśli chcesz przeszukać indeks 2 do indeksu 4, możesz to zrobić w ten sposób:

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

	}
}

W tym przypadku metoda Arrays.binarySearch() jako pierwszy argument przyjmuje tablicę, którą chcesz przeszukać, indeks początkowy jako drugi argument, indeks końcowy jako trzeci, a klucz jako czwarty. Dopóki indeks końcowy będzie mieścić się w obrębie długości tablicy, metoda powinna działać poprawnie. Ale jeśli go przekroczysz, otrzymasz wyjątek Array Index out of range . To całkiem proste, prawda? Metoda zwraca indeks elementu, jeśli zostanie znaleziony. Ale co się stanie, jeśli nie znajdzie danego elementu?

Co się stanie, gdy Arrays.binarySearch() nie znajdzie danego elementu?

Przyjrzyjmy się jeszcze raz oficjalnej dokumentacji metody Arrays.binarySearch() :

• Metoda znajduje w wynikach wyszukiwania indeks klucza, jeśli znajduje się on w tablicy w podanym zakresie; w przeciwnym razie otrzymamy (-(punkt wstawienia) - 1) .
• Punkt wstawienia definiuje się jako punkt, w którym klucz zostanie wstawiony do tablicy: indeks pierwszego elementu zakresu jest większy od klucza lub toIndex (indeks końcowy), jeżeli wszystkie elementy w zakresie są mniejsze od określony klucz.
• Należy pamiętać, że wartość zwrócona będzie większa lub równa 0, gdy klucz zostanie znaleziony.

Niezbyt jasne, prawda? Pierwsza linia mówi, że metoda zwróci indeks klucza z wyszukiwania, jeśli zostanie on znaleziony w tablicy. Jeśli nie zostanie znaleziony, wynik będzie równy wartości (-(punkt wstawienia) - 1) . W zależności od klucza wyszukiwania punkt wstawiania może mieć różne znaczenie. Powiedzmy, że mamy tablicę [5, 6, 7, 8, 9, 10] i klucz wyszukiwania równy 0 , którego wyraźnie nie ma w tablicy. W tym przypadku klucz wyszukiwania jest mniejszy niż wszystkie elementy tablicy. Ale pierwszym elementem większym niż klucz wyszukiwania jest 5 . Zatem w naszym przypadku punktem wstawienia będzie: Możesz to zaimplementować we fragmencie kodu takim jak ten:

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

Załóżmy jeszcze raz, że mamy tablicę [5, 6, 7, 8, 9, 10] i klucz wyszukiwania równy 12 , którego wyraźnie nie ma w tablicy. W tym przypadku klucz wyszukiwania jest większy niż wszystkie elementy tablicy. Tutaj punkt wstawienia będzie wyglądał następująco: Pamiętaj, że jeśli nie określisz ręcznie indeksu końcowego, metoda użyje długości tablicy jako indeksu końcowego, który w tym przypadku wynosi 6 . Możesz to zaimplementować we fragmencie kodu takim jak ten:

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

Jednak wyniki ulegną zmianie, jeśli ręcznie zdefiniujesz indeksy początkowe i końcowe:

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

	}
}

Spróbuj samodzielnie obliczyć wartości. Możesz także użyć metody Arrays.binarySearch() z symbolami takimi jak ten:

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

	}
}

Te same zasady obowiązują, jeśli określony klucz wyszukiwania nie zostanie znaleziony. Jednak podczas porównywania znaku w tablicy z danym kluczem wyszukiwania zostanie użyty kod ASCII odpowiedniego znaku. Oznacza to, że A (65) będzie mniejsze niż a (97) . Weź to pod uwagę podczas sprawdzania wyników programu.