Arrays.binarySearch: примеры (JAVA)

Короткие примеры использования

Примеры демонстрируют основные варианты: поиск в отсортированном массиве, поиск с отрицательным результатом, поиск в диапазоне и поиск объектов с компаратором.

Поиск в массиве int

int[] a = {1, 3, 5, 7, 9};
int idx = java.util.Arrays.binarySearch(a, 5);
System.out.println(idx);

2

Ключ не найден - отрицательное значение (insertion point)

int[] a = {1, 3, 5, 7, 9};
int idx = java.util.Arrays.binarySearch(a, 4);
System.out.println(idx); // -(insertionPoint) - 1

-3

Поиск в диапазоне

int[] a = {1, 2, 3, 4, 5, 6};
int idx = java.util.Arrays.binarySearch(a, 2, 5, 4); // ищет в a[2..4]
System.out.println(idx);

-4  // элемент 4 находится по индексу 3, но вне указанного диапазона, поэтому не найден

Поиск объектов с компаратором

String[] s = {"apple", "banana", "pear"};
java.util.Comparator comp = java.util.Comparator.naturalOrder();
int idx = java.util.Arrays.binarySearch(s, "banana", comp);
System.out.println(idx);

1

Поиск в несортированном массиве (неопределённый результат)

int[] a = {5, 1, 9, 3};
int idx = java.util.Arrays.binarySearch(a, 3);
System.out.println(idx);

(результат неопределённый, зависит от порядка элементов; например, -2)

Похожие средства в Java

Несколько альтернатив и их особенности:

• Collections.binarySearch(List, key)

Работает с List (например, ArrayList). Похожий контракт возвращаемого значения; требует, чтобы список был отсортирован по тому же сравнению. Удобен для коллекций, но медленнее при каждом обращении к произвольному элементу у списков с линейным доступом.

• NavigableSet / TreeSet

Наборы типа TreeSet хранят элементы в отсортированном виде и предоставляют методы (floor, ceiling, higher, lower) для поиска ближайших значений. Предпочтительнее при частых вставках/удалениях и поисках.

• Самостоятельная реализация двоичного поиска

Иногда удобна для специфичных требований (поиск первого вхождения, работа с пользовательной логикой сравнения). При необходимости контроля над алгоритмом даёт гибкость.

Аналоги в других языках и отличия

• Python (модуль bisect)

Функции bisect_left, bisect_right возвращают позицию вставки. Для проверки наличия элемента обычно: i = bisect_left(a, x); found = i < len(a) and a[i] == x.

import bisect
a = [1, 3, 5, 7]
i = bisect.bisect_left(a, 5)
print(i, a[i] == 5)

2 True

• C# (Array.BinarySearch)

Поведение и контракт возвращаемого значения близки к Java (возвращает индекс или отрицательное значение, выражающее точку вставки). Поддерживает перегрузки для диапазона и компараторов.

int[] a = {1,3,5,7};
int idx = Array.BinarySearch(a, 5);
Console.WriteLine(idx);

2

• Go (sort.Search)

В Go используется sort.Search, принимающий функцию-предикат. Возвращает позицию вставки; для проверки равенства требуется дополнительная проверка.

import "sort"
a := []int{1,3,5,7}
i := sort.Search(len(a), func(i int) bool { return a[i] >= 5 })
fmt.Println(i, i<len(a) && a[i]==5)

2 true

• JavaScript

В стандартной библиотеке нет бинарного поиска. Часто используют собственную реализацию или вспомогательные библиотеки (например, Lodash: _.sortedIndexOf, _.sortedIndex).

// пример с Lodash
_.sortedIndex([1,3,5,7], 5) // позиция вставки

2

• PHP

Стандартных бинарных функций нет, обычно выполняется sort и затем собственный бинарный поиск.

• SQL

В базах данных поиск выполняется через индексы и план выполнения; прямого аналога функции нет, но индекс обеспечивает логарифмическое время поиска в таблице.

• Kotlin

В Kotlin доступны функции Arrays.binarySearch и расширения для коллекций, поведение идентично Java, но с синтаксическими улучшениями языка и возможностью использования лямбда-компараторов.

• Lua

Нет встроенного бинарного поиска, реализуется вручную.

Типичные ошибки и примеры

Ниже перечислены частые ошибки при использовании Arrays.binarySearch и иллюстрации их проявления.

Неотсортированный массив - неожиданный результат

int[] a = {10, 1, 8, 3};
int idx = java.util.Arrays.binarySearch(a, 3);
System.out.println(idx);

(результат неопределённый, например -2)

Неправильная интерпретация отрицательного кода

int[] a = {1,3,5,7};
int r = java.util.Arrays.binarySearch(a, 4);
int insertionPoint = -r - 1; // правильно
System.out.println(r + ", " + insertionPoint);

-3, 2

Использование неконсистентного Comparator

String[] s = {"a","B","c"};
java.util.Comparator comp = (x,y) -> x.length() - y.length();
java.util.Arrays.sort(s, comp);
int idx = java.util.Arrays.binarySearch(s, "B", comp);
System.out.println(idx);

(результат может быть неожиданным, так как Comparator не даёт тот же порядок, что естественное сравнение; при смешанных критериях возможны логические ошибки)

ClassCastException при смешанных типах в Object[]

Object[] a = {"one", 2};
int idx = java.util.Arrays.binarySearch(a, "one");

Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String

Изменения и история

Метод является частью библиотеки с ранних версий Java и существенно не менялся в семантике. Начиная с Java 5–8 появились удобства языка (дженерики, лямбда-выражения), которые упростили использование перегрузок с Comparator. Для типов с плавающей запятой остаётся поведение, базирующееся на Float.compare и Double.compare. В последних релизах изменений API для Arrays.binarySearch не наблюдалось.

Расширенные и редкие варианты применения

Нахождение первой позиции вхождения среди дубликатов

int[] a = {1,2,2,2,3,4};
int idx = java.util.Arrays.binarySearch(a, 2);
// найден некоторый индекс, но нужно найти первый
if (idx >= 0) {
    while (idx > 0 && a[idx-1] == 2) idx--;
}
System.out.println(idx);

1

Нахождение соседних элементов (floor/ceiling) используя insertion point

int[] a = {1,3,5,7};
int r = java.util.Arrays.binarySearch(a, 4);
int ip = -r - 1; // insertion point
int floor = (ip - 1 >= 0) ? a[ip-1] : Integer.MIN_VALUE;
int ceiling = (ip < a.length) ? a[ip] : Integer.MAX_VALUE;
System.out.println("floor=" + floor + ", ceiling=" + ceiling);

floor=3, ceiling=5

Поиск с пользовательским компаратором для объектов

class Person {
    String name; int age;
    Person(String n, int a){name=n; age=a;}
    public String toString(){return name+":"+age;}
}

Person[] arr = {new Person("A",30), new Person("B",20), new Person("C",25)};
java.util.Comparator byAge = java.util.Comparator.comparingInt(p -> p.age);
java.util.Arrays.sort(arr, byAge);
int idx = java.util.Arrays.binarySearch(arr, new Person("X",25), byAge);
System.out.println(idx + ", " + arr[idx]);

1, B:20  // если компаратор сравнивает только по age, возвращаемый индекс указывает на элемент с совпадающим age

Обработка NaN и знакового нуля для double/float (пример с безопасным компаратором)

double[] a = {Double.NEGATIVE_INFINITY, -0.0, 0.0, Double.POSITIVE_INFINITY, Double.NaN};
// рекомендуемая практика: явно определять порядок NaN и -0.0 при необходимости
int idx1 = java.util.Arrays.binarySearch(a, 0.0);
int idx2 = java.util.Arrays.binarySearch(a, Double.NaN);
System.out.println(idx1 + ", " + idx2);

2, 4

Использование для многомерных структур через ключи

// поиск по первому элементу пары
int[][] pairs = {{1,100},{2,200},{4,400}};
int key = 3;
java.util.Comparator comp = (x,y) -> Integer.compare(x[0], y[0]);
java.util.Arrays.sort(pairs, comp);
int idx = java.util.Arrays.binarySearch(pairs, new int[]{key,0}, comp);
int insertion = (idx < 0) ? -idx - 1 : idx;
System.out.println(idx + ", insertion=" + insertion);

-3, insertion=2

Поиск и одновременная вставка (эффективность для больших массивов)

int[] a = {1,2,4,5};
int key = 3;
int r = java.util.Arrays.binarySearch(a, key);
int ip = (r >= 0) ? r : -r - 1;
int[] b = new int[a.length + 1];
System.arraycopy(a, 0, b, 0, ip);
b[ip] = key;
System.arraycopy(a, ip, b, ip+1, a.length - ip);
System.out.println(java.util.Arrays.toString(b));

[1, 2, 3, 4, 5]