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.