Алгоритм двоичного поиска в Java

1. Обзор

В этой статье мы рассмотрим преимущества двоичного поиска по сравнению с простым линейным поиском и рассмотрим его реализацию на Java.

2. Необходимость эффективного поиска

Допустим, мы занимаемся продажей вина, и миллионы покупателей посещают наше приложение каждый день.

С помощью нашего приложения покупатель может отфильтровать товары, цена которых ниже n долларов, выбрать бутылку из результатов поиска и добавить их в свою корзину. У нас есть миллионы пользователей, которые каждую секунду ищут вина с ограничением цен. Результаты должны быть быстрыми.

На бэкэнде наш алгоритм выполняет линейный поиск по всему списку вин, сравнивая предельную цену, введенную клиентом, с ценой каждой бутылки вина в списке.

Затем он возвращает товары, цена которых меньше или равна предельной цене. Этот линейный поиск имеет временную сложность O (n) .

Это означает, что чем больше винных бутылок в нашей системе, тем больше времени потребуется. Время поиска увеличивается пропорционально количеству представленных новых элементов.

Если мы начнем сохранять элементы в отсортированном порядке и искать элементы с помощью двоичного поиска, мы можем достичь сложности O (log n) .

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

3. Двоичный поиск

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

Помните - ключевым моментом здесь является то, что массив уже отсортирован.

Если поиск заканчивается тем, что оставшаяся половина оказывается пустой, ключа нет в массиве.

3.1. Итеративный импл

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

Метод runBinarySearchIteratively принимает в качестве аргументов sortedArray , key, а также младшие и высокие индексы sortedArray . Когда метод запускается в первый раз, низкий , первый индекс sortedArray, равен 0, а высокий , последний индекс sortedArray, равен его длине - 1.

Середина является средним показателем sortedArray . Теперь алгоритм работает то время как цикл , сравнив ключ со значением массива среднего показателя sortedArray .

3.2. Рекурсивный Impl

Теперь давайте посмотрим на простую рекурсивную реализацию:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

RunBinarySearchRecursively метод принимает sortedArray , ключ, с низким и высокими индексами sortedArray .

3.3. Использование массивов. binarySearch ()

int index = Arrays.binarySearch(sortedArray, key); 

SortedArray и ключ int , который должен быть найден в массиве целых чисел, передаются в качестве аргументов методу binarySearch класса Java Arrays .

3.4. Использование коллекций. binarySearch ()

int index = Collections.binarySearch(sortedList, key); 

SortedList и Integer ключ , который должен быть найден в списке объектов Integer , передаются в качестве аргументов методу binarySearch класса Java Collections .

3.5. Спектакль

Использовать ли рекурсивный или итеративный подход для написания алгоритма - это в основном вопрос личных предпочтений. Но все же вот несколько моментов, о которых нам следует знать:

1. Рекурсия может быть медленнее из-за накладных расходов на обслуживание стека и обычно занимает больше памяти.

2. Рекурсия не поддерживает стек . Это может вызвать исключение StackOverflowException при обработке больших наборов данных.

3. Рекурсия добавляет ясности коду, поскольку делает его короче по сравнению с итеративным подходом.

В идеале бинарный поиск будет выполнять меньшее количество сравнений по сравнению с линейным поиском больших значений n. Для меньших значений n линейный поиск может работать лучше, чем двоичный поиск.

Следует знать, что этот анализ носит теоретический характер и может варьироваться в зависимости от контекста.

Кроме того, алгоритму двоичного поиска нужен отсортированный набор данных, который тоже имеет свои издержки . Если мы используем алгоритм сортировки слиянием для сортировки данных, к нашему коду добавляется дополнительная сложность n log n .

Итак, сначала нам нужно хорошо проанализировать наши требования, а затем принять решение, какой алгоритм поиска лучше всего соответствует нашим требованиям.

4. Вывод

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

Пожалуйста, найдите код для руководства на GitHub.