Содержание
Бинарный поиск — это очень эффективный алгоритм поиска, который находит элемент в отсортированном массиве путем многократного сокращения диапазона поиска вдвое. В результате время выполнения является логарифмическим, или O (log n ). В этой статье рассказывается, как использовать Java Arrays.binarySearch и Collections.binarySearch для поиска в отсортированных массивах или списках массивов значительно быстрее, чем при использовании методов линейного поиска, таких как цикл for или List.contains .
Как минимум, требуются только рабочие знания массивов и списков . Знание Comparable и Comparator пригодится.
Поиск с помощью бинарного поиска
Функция двоичного поиска Java может быть найдена в API java.util.Arrays и java.util.Collections . Arrays API предоставляет реализацию для массивов.
Поиск в массиве
В простейшей форме статический метод Arrays.binarySearch принимает массив любого примитивного типа (а также объект или ссылочный тип) и ключ поиска, например:
-
static int binarySearch(int[] a, int key) -
static int binarySearch(char[] a, char key) -
static int binarySearch(Object[] a, Object key)
Методы возвращают int представляющий индекс найденного поискового ключа в массиве, или иначе отрицательное значение (значение которого я объясню через минуту), если оно не найдено.
Вот пример кода:
int[] numbers = {2, 3, 5, 7}; System.out.println("index of 5 is " + Arrays.binarySearch(numbers, 5)); // index of 5 is 2
Перед использованием функции двоичного поиска убедитесь, что массив уже отсортирован в порядке возрастания (например, с Arrays.sort метода Arrays.sort ), в противном случае результаты будут неожиданными.
Поиск диапазона
Если вы должны искать только в диапазоне указанного массива ключ поиска, вы можете использовать эту перегрузку:
Обратите внимание, что toIndex является эксклюзивным для поиска. В предыдущем примере, если вы хотите искать в массиве только индекс от 0 до 2 (включительно), вы пишете:
Arrays.binarySearch(numbers, 0, 3, 5);
Поиск с помощью компаратора
Если вы используете метод двоичного поиска для массива Object , элементы массива должны либо реализовать интерфейс Comparable либо должен быть указан Comparator :
Объект Comparator используется двоичным поиском для сравнения порядка двух объектов, чтобы он мог определить, находится ли объект перед или после другого в массиве во время поиска. Другими словами, API-интерфейсы не ограничивают массив Object в возрастающем / естественном порядке.
Массив может быть в любом порядке сортировки, если вы можете предоставить Comparator который устанавливает порядок, соответствующий порядку сортировки массива. В простейшем случае вы использовали один и тот же компаратор для сортировки массива с помощью Arrays.sort(T[] a, Comparator<? super T> c) .
Вот пример для поиска в массиве Integer в порядке убывания:
Integer[] numbers = {2, 3, 5, 7}; // sort numbers into reverse natural order, ie {7, 5, 3, 2} Arrays.sort(numbers, Collections.reverseOrder()); // search using a reverse natural order comparator System.out.println("index of 5 is " + Arrays.binarySearch(numbers, 5, Collections.reverseOrder())); // index of 5 is 1
Поиск в списке
Класс Collections Java, с другой стороны, предоставляет функцию двоичного поиска для работы со List . Две версии перегруженного метода Collections.binarySearch :
-
static int binarySearch(List<? extends Comparable<? super T>> list, T key) -
static int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
Использование этих методов аналогично Arrays.binarySearch за исключением того, что методы принимают List объектов, а не массив.
Вот пример:
List<Integer> numbers = Arrays.asList(2, 3, 5, 7); System.out.println("index of 5 is " + Collections.binarySearch(numbers, 5)); // index of 5 is 2
Предостережение: неразумно использовать бинарный поиск в
LinkedList, реализация которого позволяет только последовательный доступ к его элементам, в результате чего алгоритм бинарного поиска работает очень плохо.
Бинарный поиск для вставки
API-интерфейсы как Arrays.binarySearch и Collections.binarySearch имеют особое поведение, когда они не могут найти данный ключ поиска в указанном массиве или списке: в этом случае метод двоичного поиска в обоих классах возвращает отрицательное значение, эквивалентное - <insertion point> - 1 , где точка вставки определяется как индекс, по которому ключ поиска будет вставлен в массив или список.
Вот пример:
List<Integer> numbers = new ArrayList<>( Arrays.asList( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29)); System.out.println("index of 5 is " + Collections.binarySearch(numbers, 5)); System.out.println("index of 23 is " + Collections.binarySearch(numbers, 23)); System.out.println("index of 9 is " + Collections.binarySearch(numbers, 9)); System.out.println("index of 31 is " + Collections.binarySearch(numbers, 31));
Выход:
index of 5 is 2 index of 23 is 8 index of 9 is -5 index of 31 is -11
В этом примере целые числа 9 и 31 не существуют в списке. С возвращенным отрицательным значением 9 будет вставлено в индекс 4 , толкая исходные записи в индексах 4 и после одного слота назад. Значение 31 было бы вставлено в индекс 10 , который находится в конце списка. Если бы мы вставили 9 в список, мы могли бы написать такой код:
int pos = Collections.binarySearch(numbers, 9); if (pos < 0) { numbers.add(Math.abs(pos)-1, 9); }
Эта функция бинарного поиска особенно полезна для реализации функции вставки, например, для некоторой очереди приоритетов, которая использует массив для хранения своих записей в порядке возрастания. Точку вставки можно использовать для соответствующей вставки новой записи в очередь.
Завершение
Стандартные методы двоичного поиска Java для java.util.Arrays и java.util.Collections позволяют найти элемент или найти точку вставки для нового элемента в массиве или списке. Бинарный поиск работает только по отсортированным массивам или спискам. Он имеет логарифмическое время выполнения, что делает его очень эффективным для больших структур данных: учитывая отсортированный массив размером 100 000, максимальные необходимые шаги для бинарного поиска для поиска элемента — это log (100 000) / log (2) ≈ 17. На небольших данных структуры, дополнительные издержки могут сделать двоичный поиск медленнее, чем линейное сканирование.