Определение

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

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

Бинарный поиск работает следующим образом:

1. Выбирается средний элемент множества;

2. Если средний элемент = исходному - алгоритм закончен;

3. Если искомый элемент < среднего, оставляем левую часть множества. Если же искомый элемент > среднего, оставляем правую часть множества. Продолжаем поиск.

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

Исходный массив - $[-2, -1, 0, 1, 3, 5, 8, 10, 12, 13]$ Искомый элемент - 8

Шаг 1

Средний элемент исходного массива - 3.

Шаг 2

Сравниваем искомый элемент со средним элементом. Так как искомый элемент больше среднего, оставляем правую часть множества. Получился массив - $[5, 8, 10, 12, 13]$. Средним элемент в этом массиве - 10.

Шаг 3

Так как средний элемент больше искомого, оставляем левую часть множества. Средний элемент равняется 5.

Шаг 4

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

Сравнение бинарного поиска с простым поиском

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

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

Сложность алгоритма бинарного поиска - $log_{2} n$.

Псевдокод

Функция бинарный_поиск(массив, данные):  
    начальный_индекс = 0  
    конечный_индекс = длина(массив)  
  
    Пока начальный_индекс <= конечный_индекс:  
        средний_индекс = (начальный_индекс + конечный_индекс) // 2  
        предположение = массив[средний_индекс]  
  
        Если предположение == данные:  
            Вернуть средний_индекс  
  
        Если предположение < данные:  
            начальный_индекс = средний_индекс + 1  
  
        Иначе:  
            конечный_индекс = средний_индекс - 1  
  
    Вернуть -1

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

Аннотация:  
bin_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++

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

int bin_search(vector<int> arr, int i) {  
    int begin = 0;  
    int end = arr.size() - 1;  
      
    while (begin <= end) {  
        int mid = (begin + end) / 2;  
          
        if (arr[mid] == i)  
            return mid;  
        if (arr[mid] < i)  
            begin = mid + 1;  
        else  
            end = mid - 1;  
    }  
    return -1;  
}

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

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

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