Алгоритмы неформально. Инструкция для начинающих питонистов - [35]

upperbound = len(sorted_cabinet)

lowerbound = 0

Для начала предположим, что папка находится в середине полки. Мы импортируем математическую библиотеку Python для использования функции floor(), преобразующей дробные числа в целые. Напомню, что предположение на середине диапазона обеспечивает максимально возможный объем информации:

import math

guess = math.floor(len(sorted_cabinet)/2)

Затем необходимо проверить, было ли предположение слишком большим или малым. В зависимости от результата проверки будут выполняться разные действия. Для искомого значения будет использоваться переменная looking_for:

if(sorted_cabinet[guess] > looking_for):

    --...--

if(sorted_cabinet[guess] < looking_for):

    --...--

Если номер папки на полке слишком велик, то наше предположение становится новой верхней границей, так как искать выше смысла нет. После этого выдается другое, меньшее предположение — точнее, оно находится на середине между текущим предположением и нижней границей:

looking_for = 3

if(sorted_cabinet[guess] > looking_for):

    upperbound = guess

    guess = math.floor((guess + lowerbound)/2)

Аналогичный процесс применяется в том случае, если номер папки на полке слишком мал:

if(sorted_cabinet[guess] < looking_for):

    lowerbound = guess

    guess = math.floor((guess + upperbound)/2)

Наконец, все составляющие можно объединить в функцию binarysearch(). Функция содержит цикл while, который выполняется до пор, пока не будет найден искомый элемент (листинг 4.7).

Листинг 4.7. Реализация бинарного поиска

import math

sortedcabinet = [1,2,3,4,5,6,7,8,9,10]

def binarysearch(sorted_cabinet,looking_for):

    guess = math.floor(len(sorted_cabinet)/2)

    upperbound = len(sorted_cabinet)

    lowerbound = 0

    while(abs(sorted_cabinet[guess] - looking_for) > 0.0001):

        if(sorted_cabinet[guess] > looking_for):

            upperbound = guess

            guess = math.floor((guess + lowerbound)/2)

        if(sorted_cabinet[guess] < looking_for):

            lowerbound = guess

            guess = math.floor((guess + upperbound)/2)

    return(guess)

print(binarysearch(sortedcabinet,8))

Итоговый вывод этого кода сообщает нам, что число 8 находится в позиции 7 списка sorted_cabinet. Это правильный результат (помните, что индексы списков Python начинаются с 0). Стратегия предположений, исключающих половину оставшихся вариантов, оказывается полезной во многих областях. Например, она лежит в основе самой эффективной стратегии (в среднем) в некогда популярной настольной игре «угадай кто». К тому же она является лучшим (теоретически) способом поиска слов в большом незнакомом словаре.

Применение бинарного поиска

Помимо игр-угадаек и поиска слов, бинарный поиск используется в ряде других областей. Например, идея бинарного поиска может использоваться при отладке кода. Предположим, вы написали код, который не работает, но не уверены в том, в какой его части кроется ошибка. Для поиска проблемы можно воспользоваться стратегией бинарного поиска. Код делится надвое, и обе половины выполняются независимо. Если какая-то половина выполняется неправильно, значит, проблема кроется именно в ней. Проблемная часть снова разбивается надвое, а каждая половина проверяется отдельно, чтобы сократить количество вариантов, пока не будет найдена строка кода с ошибкой. Аналогичная идея реализована в популярной программной системе управления версиями Git в форме команды gitbisect (хотя gitbisect перебирает версии кода, разделенные во времени, вместо строк кода одной версии).

Другое применение бинарного поиска — инвертирование математических функций. Представьте, что вам нужно написать функцию для вычисления арксинуса (или обратного синуса) заданного числа. Всего в нескольких строках можно написать функцию, которая вызывает нашу функцию binarysearch() для получения правильного ответа. Для начала необходимо определить область определения, то есть значения, по которым будет проводиться поиск для нахождения конкретного значения арксинуса. Функция синуса является периодической; она принимает все возможные значения в диапазоне от –π/2 до π/2, а следовательно, область определения будет состоять из всех чисел между этими крайними точками. Затем для всех значений области определения вычисляются значения синуса. Функция binarysearch() используется для нахождения позиции числа, синус которого равен заданному числу, и возвращает значение предметной области с заданным индексом:

def inverse_sin(number):

    domain = [x * math.pi/10000 - math.pi/2 for x in list(range(0,10000))]

    the_range = [math.sin(x) for x in domain]

    result = domain[binarysearch(the_range,number)]

    return(result)

Попробуйте выполнить inverse_sin(0.9) и убедитесь в том, что функция вернет правильный ответ: около 1.12.

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