1. Обзор
В этой статье мы рассмотрим преимущества бинарного поиска по сравнению с простым линейным поиском и рассмотрим его реализацию в Java.
2. Необходимость эффективного поиска
Допустим, мы занимаемся продажей вина, и миллионы покупателей ежедневно посещают наше приложение.
Через наше приложение клиент может отфильтровать товары, цена которых ниже n долларов, выбрать бутылку из результатов поиска и добавить ее в свою корзину. У нас есть миллионы пользователей, которые каждую секунду ищут вина с ограничением цены. Результаты должны быть быстрыми.
На бэкэнде наш алгоритм выполняет линейный поиск по всему списку вин, сравнивая предельную цену, введенную клиентом, с ценой каждой бутылки вина в списке.
Затем он возвращает товары, цена которых меньше или равна предельной цене. Этот линейный поиск имеет временную сложность O(n) .
Это означает, что чем больше количество винных бутылок в нашей системе, тем больше времени это займет. Время поиска увеличивается пропорционально количеству введенных новых элементов.
Если мы начнем сохранять элементы в отсортированном порядке и искать элементы с помощью двоичного поиска, мы сможем достичь сложности O(log n) .
При бинарном поиске время, затраченное на поиск результатов, естественно увеличивается с размером набора данных, но не пропорционально.
3. Бинарный поиск
Проще говоря, алгоритм сравнивает значение key со средним элементом массива; если они неравны, то половина, в которой ключ не может быть частью, исключается, и поиск продолжается для оставшейся половины до тех пор, пока он не будет успешным.
Помните – ключевым аспектом здесь является то, что массив уже отсортирован.
Если поиск заканчивается тем, что оставшаяся половина пуста, то ключа в массиве нет.
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) {
low = mid + 1;
} else if (sortedArray[mid] > key) {
high = mid - 1;
} else if (sortedArray[mid] == key) {
index = mid;
break;
}
}
return index;
}Метод run Binary Search Итеративно принимает в качестве аргументов sorted Array , key & the low & | high индексы sorted Array . При первом запуске метода low , первый индекс sortedArray, равен 0, а high , последний индекс sortedArray, равен его длине – 1.
middle – это средний индекс отсортированного массива . Теперь алгоритм запускает цикл while , сравнивающий ключ со значением массива среднего индекса отсортированного массива .
3.2. Рекурсивная Реализация
Теперь давайте также рассмотрим простую рекурсивную реализацию:
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);
}
}
Метод run Binary Search Recursively принимает sorted Array , key, the low and high индексы sorted Array .
3.3. Использование Arrays.BinarySearch()
int index = Arrays.binarySearch(sortedArray, key);
Сортированный массив и ключ int |, который должен быть найден в массиве целых чисел, передаются в качестве аргументов методу BinarySearch класса Java Arrays .
3.4. Использование Collections.BinarySearch()
int index = Collections.binarySearch(sortedList, key);
Сортированный список & an Integer | key , который должен быть найден в списке объектов Integer , передаются в качестве аргументов методу BinarySearch класса Java Collections .
3.5. Производительность
Использовать ли рекурсивный или итеративный подход для написания алгоритма-это в основном вопрос личных предпочтений. Но все же есть несколько моментов, о которых мы должны знать:
1. Рекурсия может быть медленнее из – за накладных расходов на поддержание стека и обычно занимает больше памяти
2. Рекурсия не является стеком –
дружественной. Это может вызвать StackOverflowException
при обработке больших наборов данных
3. Рекурсия добавляет ясности коду, так как делает его короче по сравнению с итеративным подходом
В идеале двоичный поиск будет выполнять меньшее количество сравнений в отличие от линейного поиска больших значений n. Для меньших значений n линейный поиск может работать лучше, чем двоичный.
Следует знать, что этот анализ носит теоретический характер и может варьироваться в зависимости от контекста.
Кроме того, алгоритм бинарного поиска нуждается в отсортированном наборе данных, который также имеет свои издержки . Если мы используем алгоритм сортировки слиянием для сортировки данных, то в наш код добавляется дополнительная сложность n log n .
Поэтому сначала нам нужно хорошо проанализировать наши требования, а затем принять решение о том, какой алгоритм поиска лучше всего соответствует вашим требованиям.
4. Заключение
Этот учебник продемонстрировал реализацию алгоритма бинарного поиска и сценарий, в котором было бы предпочтительнее использовать его вместо линейного поиска.
Пожалуйста, найдите код для учебника на GitHub .