22 Дек


2018

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

Столкнулся с алгоритмической задачей, частью решения которого было использование бинарного поиска. Использовал я готовую библиотеку. Момент самого алгоритма как-то выпал из моего образования, на деле все оказалось очень тривиально, после формального описание у меня сразу возникли мысли типа "пфф, да это можно забацать за 15 минут", (спойлер - можно), хотя на хабре было выссказывание что только 10% программистов могут реализовать алгоритм (мне кажется это явное преуменьшение, возможно речь идет об имплементации с 1 раза).

В общем алгоритм ищет элемент в упорядоченном массиве. Делит его индексы пополам, если элемент с этим индексом равен искомому возвращаем его, если больше искомого элемента то ищем в левой части, если меньше то в правой. Изначально я реализовал что-то наподобие этого:

def binary_search(l, el):
    if el > l[len(l)-1] or el < l[0]:
        return False
    midl = round(len(l) / 2)
    if l[midl] > el:
        return binary_search(l[:midl], el)
    elif l[midl] < el:
        return binary_search(l[midl:], el)
    return True

И в принципе это работает, рекурсивно обходим, проверяем в срезе наличие элемента, в общем это больше похоже на функцию is_contain. Неплохо было бы добавить индекс найденного элемента. Т.к. я использую питон то отрицательных индексов в массиве быть не может, следовательно сделаем возврат -1 если значение отсутствует в передаваемом списке.

def bs(l, el, left, right):
    pos = round((left + right) / 2)
    if l[pos] < el:
        return bs(l, el, pos, right)
    elif l[pos] > el:
        return bs(l, el, left, pos)
    return pos

def binary_search(l, el):
    if el < l[0] or el > l[len(l)-1]:
        return -1
    return bs(l, el, 0, len(l))

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

сортировка
Алгоритмы