Дай 10 !)

понедельник, 4 апреля 2011 г.

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


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

Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Бинарный поиск позволяет найти данный элемент в отсортированном массиве или определить, что он не встречается в данном массиве за 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

10 комментариев:

  1. Очень доступно все объяснил. Спасибо

    ОтветитьУдалить
  2. Есть вопрос, наверно я чего-то не понял. А почему в случае, если в функцию попадает массив с четным кол-вом значений, не вызывается исключение? Ведь тогда в li[m] под переменной m попадает дробное число. Надеюсь достаточно хорошо изложил свой вопрос. Буду благодарен если кто-либо просветит меня в этой теме. Заранее спасибо!

    ОтветитьУдалить
    Ответы
    1. Ой извините, я сам разобрался и понял что функция int округляет вводное значение до целого числа)

      Удалить
    2. Точнее это происходит в случае указания оператора деления в аргументе функции, но это не точно, если так отпишитесь господа)

      Удалить
  3. if i > j:
    return 'Нет такого'

    Эта строчка никогда не сработает потому что условие while, расположенное выше не позволит стать i > j

    ОтветитьУдалить
    Ответы
    1. Дурак что ли? Прогони алгоритм вручную, тогда поймёшь, что не прав

      Удалить
  4. Дело Alex говорит. Не работает функция если не исправить в while на "i <= j"

    ОтветитьУдалить
  5. Твой алгоритм не работает. Удали его лучше.

    ОтветитьУдалить