Метод binarySearch

Метод binarySearch класса Collections выполняет бинарный поиск указанного элемента в отсортированном списке и возвращает его индекс. Если элемент найден, метод возвращает его позицию в списке. Если элемент не найден, метод возвращает отрицательное число, которое вычисляется по формуле -(точка вставки) - 1, где точка вставки - это индекс, по которому элемент должен был бы находиться, чтобы список оставался отсортированным.

В первый параметр мы передаем список, в котором выполняется поиск. Список должен быть отсортирован по возрастанию, иначе результат будет непредсказуемым. Во второй параметр мы передаем искомый элемент. Существует также перегрузка метода, которая третьим параметром принимает компаратор для сравнения элементов.

Синтаксис

Collections.binarySearch(list, key)
Collections.binarySearch(list, key, comparator)

Пример

Давайте выполним поиск элемента 3 в отсортированном списке:

import java.util.Collections;
import java.util.List;

public class Main
{
	public static void main(String[] args)
	{
		List<Integer> list = List.of(1, 2, 3, 4, 5);
		int res = Collections.binarySearch(list, 3);
		System.out.println(res);
	}
}

Результат выполнения кода:

2

Пример

Давайте выполним поиск элемента 6, которого нет в списке. Метод вернет отрицательное число:

import java.util.Collections;
import java.util.List;

public class Main
{
	public static void main(String[] args)
	{
		List<Integer> list = List.of(1, 2, 3, 4, 5);
		int res = Collections.binarySearch(list, 6);
		System.out.println(res);
	}
}

Результат выполнения кода:

-6

Отрицательное значение -6 означает, что элемент должен был бы находиться на позиции 5, так как -(5) - 1 = -6.

Пример

Давайте выполним поиск строки "c" в отсортированном списке строк:

import java.util.Collections;
import java.util.List;

public class Main
{
	public static void main(String[] args)
	{
		List<String> list = List.of("a", "b", "c", "d", "e");
		int res = Collections.binarySearch(list, "c");
		System.out.println(res);
	}
}

Результат выполнения кода:

2

Смотрите также

класс Collections,
который содержит статические методы для работы с коллекциями
метод sort,
который сортирует список по возрастанию
метод reverse,
который меняет порядок элементов на обратный
метод shuffle,
который перемешивает элементы списка случайным образом