Метод Arrays.binarySearch()

Метод Arrays.binarySearch() из класса java.util.Arrays выполняет бинарный (двоичный) поиск и возвращает индекс заданного значения в массиве. Если искомый элемент не найден, метод возвращает отрицательное число -(insertionPoint) - 1, где insertionPoint — позиция, в которую элемент мог бы быть вставлен. Главное требование: массив должен быть отсортирован по возрастанию, иначе результат вызова не определён.

Как работает Arrays.binarySearch()

Бинарный поиск на каждом шаге сравнивает искомое значение с элементом в середине массива и отбрасывает половину, в которой значения гарантированно не подходят. Поэтому binarySearch в Java находит элемент за O(log n) сравнений — на массиве из миллиона элементов достаточно примерно 20 шагов, тогда как линейный перебор в худшем случае потребует миллион.

import java.util.Arrays;

public class BinarySearchExample1 {
    public static void main(String[] args) {
        int[] array1 = {10, 20, 30, 40};
        int pos1 = Arrays.binarySearch(array1, 20);
        int pos2 = Arrays.binarySearch(array1, 25);
        System.out.println(pos1);
        System.out.println(pos2);
    }
}

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

1
-3

Элемент 20 найден по индексу 1. А вот значения 25 в массиве нет — и здесь начинается самое интересное.

Что возвращает метод, если элемент не найден

Отрицательный результат — это не просто «флаг неудачи», он несёт полезную информацию. Формула: -(insertionPoint) - 1, где точка вставки (insertion point) — индекс первого элемента, который больше искомого значения. В примере выше значение 25 должно было бы стоять на позиции 2 (между 20 и 30), поэтому метод вернул -(2) - 1 = -3.

Из отрицательного результата легко восстановить точку вставки — это удобно, когда нужно вставить элемент, сохранив порядок:

int result = Arrays.binarySearch(array1, 25); // -3
if (result < 0) {
    int insertionPoint = -result - 1;         // 2
    System.out.println("Вставить на позицию: " + insertionPoint);
}

Смещение на единицу нужно, чтобы отличить «не найден, точка вставки 0» (результат -1) от «найден по индексу 0» (результат 0).

Перегрузки метода binarySearch

Класс Arrays содержит перегрузки binarySearch для всех числовых примитивов (int, long, double и других), для char, а также для массивов объектов. Полный список — в официальной документации Oracle.

Поиск в части массива

Перегрузка с параметрами fromIndex и toIndex ищет только в указанном диапазоне: начальный индекс включается, конечный — нет. Отсортированным должен быть именно этот диапазон:

import java.util.Arrays;

public class BinarySearchExample2 {
    public static void main(String[] args) {
        int[] array = {5, 10, 15, 20, 25, 30};
        // Ищем 20 только среди индексов 1, 2 и 3
        int pos = Arrays.binarySearch(array, 1, 4, 20);
        System.out.println(pos); // 3
    }
}

Поиск объектов и Comparator

Для массивов объектов без компаратора используется естественный порядок — элементы должны реализовывать интерфейс Comparable, как, например, String или Integer:

import java.util.Arrays;

public class BinarySearchExample3 {
    public static void main(String[] args) {
        String[] names = {"Anna", "Boris", "Ivan", "Olga"};
        int pos = Arrays.binarySearch(names, "Ivan");
        System.out.println(pos); // 2
    }
}

Если массив отсортирован не в естественном порядке (например, по убыванию), нужно передать тот же Comparator, которым выполнялась сортировка:

import java.util.Arrays;
import java.util.Comparator;

public class BinarySearchExample4 {
    public static void main(String[] args) {
        Integer[] numbers = {40, 30, 20, 10};
        int pos = Arrays.binarySearch(numbers, 20, Comparator.reverseOrder());
        System.out.println(pos); // 2
    }
}

На чём чаще всего ошибаются

• Неотсортированный массив. Метод не проверяет порядок элементов — это было бы дорого. Он просто выполняет алгоритм и может вернуть отрицательное число даже для элемента, который в массиве есть.
• Дубликаты. Если искомое значение встречается несколько раз, нет никакой гарантии, какой именно из индексов будет возвращён — не обязательно первый.
• Comparator не совпадает с порядком сортировки. Массив, отсортированный по убыванию, нельзя искать перегрузкой без компаратора — сравнивать нужно тем же правилом, по которому массив упорядочен.
• Прямое сравнение с -1. Проверка if (result == -1) ловит только случай «точка вставки 0». Правильная проверка «не найдено» — result < 0.
• null и объекты без Comparable. Поиск null или объектов, не реализующих Comparable (в перегрузке без компаратора), приводит к NullPointerException или ClassCastException.

Презентация с видео на Patreon →