Кофе-брейк #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). В зависимости от ключа поиска, insertion point может иметь разные значения. Предположим, у нас есть массив [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). Учтите это при перекрестной проверке выходных данных вашей программы.