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

Алгоритмы поиска занимаются определением того, содержит ли массив (или список) заданное значение, и в каком месте массива это значение находится. Поиск используется для упорядоченных последовательностей. Слово "бинарный" говорит о том, что на каждом шаге работы алгоритма просматриваемый массив делится на две части.

Алгоритм:

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

Если ограничится целыми числами и не использовать стандартные функции Python, то для поиска значения value в списке lst получим:

low = 0
high = len(lst)-1
while low <= high: 
    mid = (low+high)//2
    if lst[mid] > value: 
        high = mid-1
    elif lst[mid] < value: 
        low = mid+1
    else: 
        break

if lst[mid] == value:
    print "Index:", mid
else:
    print "Not found"

Кроме того, очевидно, что можно применить рекурсию. Однако, это не слишком интересно, потому что с помощью стандартных функций Python достичь цели можно в одну строчку:

print [i for i,v in enumerate(lst) if v == value]

В отличие от первого, этот код дает индексы всех вхождений искомого значения.

Кроме того, в стандартной библиотеке Python есть модуль bisect.