Бинарный поиск (двоичный) - алгоритм нахождения заданного элемента в отсортированном массиве. Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект.Так продолжается до тех пор пока мы либо не найдем искомый элемент, либо пока нужная часть массива не окажется пустой.

Описание алгоритма

Алгоритм бинарного поиска элемента $$key$$ в отсортированном массиве $$a$$ на отрезке $$[l \ldots r]$$ можно описать следующими шагами:

Если длина отрезка $$[l \ldots r]$$ отрицательна, то искомого элемента в массиве нет, вернуть $$-1$$;
Находим элемент $$mid$$ стоящий в середине отрезка;
Сравниваем данный элемент с искомым в массиве;
Если элементы совпадают, вернуть соответствующий индекс;
Если элемент стоящий в середине больше искомого, то обрабатываем правую половину, иначе левую.

Визуализация работы алгоритма

Пусть требуется найти элемент равный $$35$$ в массиве $$A = [4, 9, 25, 28, 34, 35, 50, 67, 70]$$.

Находим элемент стоящий в середине отрезка, им является число $$mid = 34$$ с индексом $$4$$.

Поскольку элемент стоящий в середине отрезка меньше чем $$35$$, то все элементы стоящие слева от него так же меньше искомого. Таким образом, искомый элемент может находится только в правой половине от $$mid + 1$$ до $$r$$.

Находим элемент стоящий в середине отрезка $$[mid + 1, \ldots, r]$$, им является число $$50$$ с индексом $$6$$.

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

На следующей итерации у нас остается отрезок длины $$1$$, и элемент стоящий в середине равен искомому, индекс которого равен $$5$$.

Рекурсивная реализация алгоритма

int BinarySearch(int arr[], int l, int r, int x)
    {
        if (r >= l)
        {
            int mid = l + (r - l) / 2;

            if (arr[mid] == x)
               return mid;

            if (arr[mid] > x)
               return BinarySearch(arr, l, mid - 1, x);

            return BinarySearch(arr, mid + 1, r, x);
        }

        return -1;
}

Итеративная реализация алгоритма

int BinarySearch(int arr[], int l, int r, int x)
    {
        while (l <= r)
        {
            int m = l + (r - l) / 2;

            if (arr[m] == x)
                return m;

            if (arr[m] < x)
                l = m + 1;
            else
                r = m - 1;
        }

        return -1;
    }

Правосторонний / левосторонний бинарный поиск

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

int LeftBinarySearch(int[] a, int l, int r, int key)
{  
    while (l < r) 
    {
        int mid = l + (r - l) / 2;

        if(a[mid] < key)
            l  = mid;
        else
            r = mid;
    }
    return a[r] == key ? r : -1;
}

В случае правостороннего поиска изменится знак сравнения при сужении границ на $$a[mid] \leq key$$

Производительность и анализ сложности

Поскольку на каждой итерации бинарного поиска мы отбрасываем половину элементов массива, то в худшем случае нам потребуется $$[\log n] + 1$$ шагов, чтобы найти нужный элемент, либо сказать, что его нет.

Рекуррентное уравнение выражающее время работы бинарного поиска имеет вид $$T(n)=T(n/2)+c$$. С помощью основной теоремы (случай 2) находим $$T(n) = \Theta(\log n)$$. Таким образом алгоритм бинарного поиска, работает в худшем случае за логарифмическое время.

Поскольку логарифмическая функция растет медленно, то бинарный поиск является очень эффективным алгоритмом поиска. К примеру, если у нас есть массив содержащий всех людей в мире, отсортированных по имени, мы можем найти любого человека менее чем за 35 шагов.

Реализация бинарного поиска в стандартных библиотеках

В стандартной библиотке STL (C++) реализованы все виды бинарного поиска: binary_search, lower_bound, upper_bound, equal_range. В Java и .NET бинарный поиск представлен в виде методов Arrays.binary_search и Array.BinarySearch которые возвращают индекс первого из найденных элементов. Аналогов для lower_bound, upper_bound, equal_range в Java и C# нет.

Тонкости алгоритма

Несмотря на простоту, алгоритм имеем несколько тонких моментов.

Нахождени середины с помощью формулы $$\dfrac{l+r}{2}$$ может приводить к переполнению типа данных. Данная бага была в реализации бинарного поиска в Java 5 и .NET 1.0.
Если элемент больше максимального из представленных в массиве, то в случае если правая граница массива R равна максимальному из возможных значений своего типа, то происходит переполнение.
Проверка на массивах малых размеров 1, 2 и 3 элемента

Характеристики алгоритма

Класс алгоритма	Алгоритм поиска
Парадигма алгоритма	Разделяй и властвуй
Структура данных	Отсортированный массив
Худший случай	$$\mathcal{O}(\log n)$$
Лучший случай	$$\mathcal{O}(1)$$
Средний случай	$$\mathcal{O}(\log n)$$
Затраты на память	$$\mathcal{O}(1)$$ для итеративной версии, $$\mathcal{O}(\log n)$$ для рекурсивной версии

Приложение и задачи решаемые с помощью бинарного поиска

Практические приложения бинарного поиска разнообразны:

Численное нахождение приближённого решения уравнений $$f(x)= C$$, где $$y=f(x)$$ - монотонная функция. Метод известен как вещественный бинарный поиск или метод бисекции;
Нахождение корня $$n$$ - ой степени из заданного положительного числа $$x$$: $$\sqrt[n]{x}$$;
Нахождение экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до $${\displaystyle \varepsilon }$$ можно за время $${\displaystyle \log {2} 1/\varepsilon } $$. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт $${\displaystyle 1+\log{2} N} $$ времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

Бинарный поиск