Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Бинарный поиск - это алгоритм поиска определённого элемента в отсортированной последовательности путём деления диапазона поиска пополам до теx пор, пока не найдено искомое значение в середине диапазона.

---

Сферы применения

1. Поиск в отсортированных последовательностях Основное применение бинарного поиска - нахождение индекса элемента в отсортированной последовательности. Поскольку сложность алгоритма составляет $O(log⁡$ $n)$, он значительно быстрее линейного поиска.

2. Нахождение границ значений Бинарный поиск применяется для поиска верхней или нижней границы значения в отсортированном последовательности, например, для определения диапазона значений, удовлетворяющих определенному условию.

3. Оптимизация задач Бинарный поиск можно использовать для поиска оптимального решения в задачах, где оптимизация параметров сводится к проверке выполнения условия на промежутке. Например, нахождение минимума или максимума на определенном интервале, а также поиск минимального или максимального значения, удовлетворяющего условию, например, минимальный радиус для покрытия всех точек.

---

Принцип работы алгоритма

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

Шаги работы алгоритма:

1. Определение границ. Выбираются границы поиска - первая и последняя позиции в отсортированной последовательности, где находится предполагаемый элемент.

2. Определение среднего элемента. На каждом этапе вычисляется элемент, находящийся в середине диапазона между первой и последней позициями.

3. Сравнение среднего элемента с искомым значением. Средний элемент сравнивается с искомым значением:

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

4. Сужение диапазона поиска. После каждого сравнения диапазон поиска сужается вдвое. Либо правая, либо левая граница сдвигается к середине в зависимости от результата сравнения.

---

Особенности

1. Последовательность должна быть отсортирована.

2. Подходит только для структур, поддерживающих случайный доступ (например, массивы или списки, но не линейные однонаправленные списки).

3. Для последовательностей с одинаковыми элементами может потребоваться модификация, чтобы найти первое или последнее вхождение.

---

Вычислительная сложность

Бинарный поиск - это эффективный алгоритм с временной сложностью $O(log⁡n)$ и пространственной сложностью $O(1)$. Благодаря уменьшению диапазона поиска вдвое на каждом шаге, он значительно быстрее, чем линейный поиск $O(n)$, при работе с большими объемами отсортированных данных.

Пошаговое доказательство

Шаг 1: Определение границ

На первом этапе алгоритм определяет начальные границы поиска - первую и последнюю позиции в последовательности. Этот шаг выполняется за $O(1)$, так как это простое присваивание значений.

Шаг 2: Определение среднего элемента

На каждом шаге алгоритм вычисляет индекс среднего элемента как: $\text{middle} = \left\lfloor \frac{\text{left} + \text{right}}{2} \right\rfloor$

Это арифметическая операция, которая выполняется за $O(1)$.

Шаг 3: Сравнение среднего элемента с искомым значением

Алгоритм сравнивает значение среднего элемента с искомым значением. Это также операция, выполняемая за $O(1)$.

Шаг 4: Сужение диапазона поиска

После сравнения диапазон поиска уменьшается вдвое, что требует обновления границ: сдвигается либо левая, либо правая граница. Это изменение также занимает $O(1)$.

Общее количество итераций

Каждая итерация алгоритма делит диапазон поиска пополам. Для последовательности длиной nn, число делений до сужения диапазона до 1 элемента определяется формулой: $k=⌈log⁡2n⌉$, где $k$ — количество итераций, необходимое для завершения работы алгоритма, а $log⁡2n$ — двоичный логарифм от $n$.

Таким образом, алгоритм выполняет не более $⌈log⁡2n⌉$ итераций.

---

Пространственная сложность

В итеративной реализации алгоритм использует фиксированное количество переменных:

1. low - которая указывает на начало рассматриваемого диапазона
2. high - которая указывает на конец рассматриваемого диапазона
3. mid - которая указывает на элемент в середине рассматриваемого диапазона

Таким образом, дополнительная память алгоритма: $O(1)$.

---

Схематическая работа алгоритма

Шаг первый

Определяем границы поиска, где находится предполагаемый элемент.

    1  2  3  4  5

Элемент, который необходимо найти:

    1

Шаг второй

Определение среднего элемента. В данном случае элемент находящийся в середине диапазона между первой и последней позицией - 3.

    1  2  3  4  5

Шаг третий

Нужно сравнить выбранный элемент с искомым.

    13< Необходимо выбрать часть объектов последовательности, исходя из результата сравнения. В данном случае объект из середины последовательности больше выбранного, поэтому нужно выбрать все объекты, которые меньше взятого.

Шаг четвёртый

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

---

Псевдокод

Аннотация:
binary_search - функция бинарного поиска
array - последовательность в котором происходит поиск
search_element - искомый элемент
begin - левая граница поиска
end - правая граница поиска
middle_element - средний элемент

функция binary_search(array, search_element)
    begin <- 0
    end <- длина array

    пока begin <= end
        middle_element <- средний элемент последовательности

        если search_element == middle_element
            то вернуть индекс middle_element

        если search_element < middle_element
            то begin = индекс middle_element + 1
            
        если search_element < middle_elemen
            то end = индекс end - 1

    если search_element нет в последовательности, то
        вернуть -1

---

Реализация на Python

Аннотация:
binary_search - функция бинарного поиска
array - отсортированная последовательность, в которой происходит поиск
data - искомый элемент
begin - левая граница поиска
end - правая граница поиска
middle - средний элемент
guess - выбираемый элемент

def bin_search(array, data):
    begin = 0  
    end = len(array) - 1  
    
    while begin <= end:  
        middle = (begin + end) // 2  
        guess = array[middle] 
         
        if guess == data:  
            return middle  
        
        if guess < data:  
            begin = middle + 1  
        else:  
            end = middle - 1  
            
    return -1

---

Олимпиадная реализация на C++

Аннотация:
bs - функция бинарного поиска
arr - отсортированная последовательность, в которой происходит поиск
val - искомый элемент
begin - левая граница поиска
end - правая граница поиска
mid - средний элемент

#include <iostream>
#include <vector>

int bs(const std::vector<int>& arr, int val) {
    int begin = 0;
    int end = arr.size() - 1;

    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        if (arr[mid] == val)
            return mid;
        if (arr[mid] < val)
            begin = mid + 1;
        else 
            end = mid - 1;
    }

    return -1;
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename - шаблонный тип данных параметра
binary_search - функция бинарного поиска
array - отсортированная последовательность, в которой происходит поиск
data - искомый элемент
begin - левая граница поиска
end - правая граница поиска
middle - средний элемент
guess - выбираемый элемент

#include <iostream>
#include <vector>

template <typename T>
int binary_search(const std::vector<T>& array, T data) {
    int begin = 0;
    int end = array.size() - 1;
    
    while (begin <= end) {
        int middle = begin + (end - begin) / 2;
        T guess = array[middle];
        
        if (guess == data)
            return middle;
            
        if (guess < data)
            begin = middle + 1;
        else 
            end = middle - 1;
    }
    
    return -1;
}