Алгоритм бинарного поиска в 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 - low) / 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;
}

Метод runBinarySearchIteratively принимает в качестве аргументов sortedArray , ключ и нижний и верхний индексы sortedArray . Когда метод запускается в первый раз, low , первый индекс sortedArray, равен 0, а high , последний индекс sortedArray, равен его длине — 1.

Middle — это средний индекс sortedArray . Теперь алгоритм запускает цикл while , сравнивая ключ со значением массива среднего индекса sortedArray .

Обратите внимание, как генерируется средний индекс (int mid = low + ((high – low) / 2) . Это необходимо для чрезвычайно больших массивов. Если средний индекс генерируется просто путем получения среднего индекса (int mid = (low + high) / 2) может произойти переполнение для массива, содержащего 2 ^30 или более элементов, поскольку сумма low + high может легко превысить максимальное положительное значение int .

3.2. Рекурсивная реализация

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

public int runBinarySearchRecursively(
  int[] sortedArray, int key, int low, int high) {
    int middle = low  + ((high - low) / 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. Использование массивов. бинарный поиск()

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

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

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

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 .