Кава-брейк #156. Як використовувати метод Arrays.binarySearch() в Java

Джерело: FreeCodeCamp Завдяки цій статті ви дізнаєтесь, як використовувати метод Arrays.binarySearch() у мові Java.

Що таке Arrays.binarySearch() у Java?

Офіційна документація за методом Arrays.binarySearch() говорить:

• Цей метод шукає у вказаному масиві байтів вказане значення, використовуючи алгоритм двійкового пошуку.
• Масив має бути відсортований (за методом sort(byte[]) ) перед виконанням виклику. Якщо його не відсортовано, результати не будуть визначені.
• Якщо масив містить кілька елементів із зазначеним значенням, немає гарантії, який з них буде знайдено.

Простіше кажучи, метод Arrays.binarySearch() може шукати заданий елемент у відсортованому масиві та повертати його індекс, якщо його знайдено.

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

	}
}

Arrays.binarySearch() метод приймає масив, який ви хочете знайти, як перший аргумент, і ключ, який ви шукаєте, як другий аргумент. Результатом зазначеної вище програми буде: Пам'ятайте, що метод повертає індекс знайденого елемента, а чи не сам елемент. Таким чином ви можете зберегти індекс у вигляді цілого числа, подібного до того, який використовується в цьому прикладі. За замовчуванням метод використовує перший індекс масиву як початкову точку пошуку і довжину масиву як кінцеву точку пошуку. У цьому випадку початковий індекс дорівнює 0, а кінцевий індекс — 6. Замість використання початкового та кінцевого індексів за умовчанням ви можете визначити їх самостійно. Наприклад, якщо ви хочете виконати пошук від індексу 2 до індексу 4, це можна зробити так:

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

	}
}

У цьому випадку метод Arrays.binarySearch() приймає масив, який ви хочете знайти, як перший аргумент, початковий індекс - як другий аргумент, кінцевий індекс - як третій і ключ - як четвертий. Поки ви зберігаєте кінцевий індекс у межах довжини масиву, метод має працювати нормально. Але якщо ви його перевищите, отримаєте виняток Array index out of range . Все досить просто, правда? Метод повертає індекс елемента, якщо його знайдено. Але що станеться, якщо він не знайде цей елемент?

Що відбувається, коли Arrays.binarySearch() не знаходить цього елемента?

Давайте ще раз звернемося до офіційної документації за методом Arrays.binarySearch() :

• Метод знаходить індекс ключа у результатах пошуку, якщо він міститься у масиві в межах зазначеного діапазону; інакше отримуємо (-(insertion point) – 1) .
• Точка вставки визначається як точка, в якій ключ буде вставлений в масив: індекс першого елемента в діапазоні більше, ніж ключ, або toIndex (кінцевий індекс), якщо всі елементи в діапазоні менші за вказаний ключ.
• Зверніть увагу, що значення, що повертається буде більше або дорівнює 0 тільки тоді, коли ключ знайдений.

Не дуже зрозуміло, правда? У першому рядку вказано, що метод поверне індекс ключа з пошуку, якщо його буде знайдено в масиві. Якщо ж він не знайдений, то вихід дорівнюватиме значенню (-(insertion point) - 1) . Залежно від ключа пошуку, введення пункту може мати різні значення. Припустимо, ми маємо масив [5, 6, 7, 8, 9, 10] і ключ пошуку 0 , якого явно немає в масиві. У цьому випадку ключ пошуку менший, ніж усі елементи масиву. Але першим елементом, який більший за ключ пошуку, є 5 . Таким чином, у нашому випадку insertion point буде: Ви можете реалізувати це у фрагменті коду таким чином:

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

Давайте знову припустимо, що ми маємо масив [5, 6, 7, 8, 9, 10] і ключ пошуку 12 , якого явно немає в масиві. У цьому випадку ключ пошуку більше, ніж усі елементи масиву. Тут insertion point буде таким: Пам'ятайте, що якщо ви не визначаєте кінцевий індекс вручну, то метод використовує довжину масиву як кінцевий індекс, який в даному випадку дорівнює 6 . Ви можете реалізувати це у фрагменті коду таким чином:

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

Однак результати зміняться, якщо ви визначите початковий та кінцевий індекси вручну:

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

	}
}

Спробуйте розрахувати значення самостійно. Ви також можете використовувати метод Arrays.binarySearch() з такими символами:

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

	}
}

Ті ж принципи застосовуються і в тому випадку, коли заданий пошуковий ключ не знайдений. Але при порівнянні між символом у масиві та заданим пошуковим ключем використовуватиметься ASCII-код відповідного символу. Тобто A (65) буде менше, ніж a (97) . Врахуйте це під час перехресної перевірки вихідних даних вашої програми.