Двоичный (бинарный) поиск элемента в массиве

Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе). Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
*-Нравится статья? Кликни по рекламе! :)

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

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

1.  Находится средний элемент последовательности. Для этого первый и последний элементы связываются с переменными, а средний вычисляется.
2.  Средний элемент сравнивается с искомым значение. В зависимости от того, больше оно или меньше среднего элемента, дальнейший поиск будет происходить лишь в левой или правой половинах массива. Если значение среднего элемента окажется равным искомому, то поиск завершен.
3.  Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.
4.  Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется уже для данной последовательности.

Переменные i и j содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент.

def BinSearch(li, x):
    i = 0
    j = len(li)-1
    m = int(j/2)
    while li[m] != x and i < j:
        if x > li[m]:
            i = m+1
        else:
            j = m-1
        m = int((i+j)/2)
    if i > j:
        return 'Нет такого'
    else:
        return m

Замечательный труд Никлауса Вирта - Алгоритмы и структуры данных, написанный в век, когда любая операция сравнения и перестановки имела огромное значение, описывает модифицированную реализацию метода.

В ней мы избавимся от проверки li[m] != x, которая выполняется каждый цикл. Для этого он предлагает отказаться от "наивного" желания закончить поиск сразу после нахождения искомого значения, а дождаться схождения левой и правой границ и сравнить найденный элемент с искомым, поняв нашли или нет. Т.к. всего шагов logN , то он считает это решение целесообразным.

def BinSearchVirt(li, x):
    i = 0
    j = len(li)-1
    while i < j:
        m = int((i+j)/2)
        if x > li[m]:
            i = m+1
        else:
            j = m
    #тут не важно j или i
    if li[j] == x:
        return j
    else:
        return None

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


Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Практические приложения метода:

• Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
• Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.

Немножко о производительности
Для сравнения, одухотворения и просто ради полезности, вынес этот вопрос в свою другую статью!)

Использованная литература: 
1.) Вики Двоиный поиск
2.) http://younglinux.info/algorithm/dichotomy
3.) http://algolist.manual.ru/search/bin_search.php