На этом шаге мы закончим изучение этого вопроса.
Код
А теперь мы реализуем алгоритм бинарного поиска в одной строке кода (пример 6.13)!
Пример 6.13. Однострочная реализация алгоритма бинарного поиска
## Данные l = [3, 6, 14, 16, 33, 55, 56, 89] x = 33 ## Однострочник (1) bs = lambda l, x, lo, hi: -1 if lo > hi else \ (2) (lo + hi) // 2 if l[(lo + hi) // 2] == x else \ (3) bs(l, x, lo, (lo + hi) // 2 - 1) if l[(lo + hi) // 2] > x else \ (4) bs(l, x, (lo + hi) // 2 + 1, hi) ## Результат print(bs(l, x, 0, len(l) - 1))
Угадайте, какие результаты вернет этот фрагмент кода!
Принцип работы
Благодаря тому, что бинарный поиск естественным образом подходит для реализации рекурсивного подхода, изучение данного однострочника укрепит ваше понимание этого важного понятия теории computer science. Отметим, что мы разбили данное однострочное решение на четыре строки ради удобства чтения, хотя, конечно, вы можете записать его в одной строке кода. В данном однострочнике используется рекурсивный способ реализации алгоритма бинарного поиска.
Мы создаем новую функцию bs с помощью оператора lambda с четырьмя аргументами: l, x, lo и hi (1) . Первые два аргумента l и x представляют собой переменные, содержащие отсортированный список и значение для поиска. Аргументы lo и hi задают минимальный и максимальный индекс текущего подсписка, в котором производится поиск значения x. На каждом уровне рекурсии код проверяет подсписок, заданный индексами lo и hi, все уменьшающийся по мере увеличения индекса lo и уменьшения индекса hi. После конечного количества шагов условие lo > hi становится True. Просматриваемый подсписок пуст - и мы не нашли значение х. Это граничный случай нашей рекурсии. Поскольку мы не нашли элемент х, то возвращаем -1, указывая, что искомого элемента не существует.
Для поиска срединного элемента подсписка мы прибегнем к формуле (lo + hi) // 2. Если он оказывается искомым, то возвращаем его индекс (2). Обратите внимание, что здесь используется целочисленное деление для округления вниз к ближайшему целочисленному значению, которое можно применять в качестве индекса списка.
Если срединный элемент больше желаемого значения, значит, все элементы справа тоже больше него, поэтому можно произвести рекурсивный вызов функции, но изменить индекс hi так, чтобы далее анализировать только элементы списка слева от срединного элемента (3) .
Аналогично, если срединный элемент меньше желаемого значения, то можно не просматривать элементы слева от него, поэтому можно произвести рекурсивный вызов функции, но изменить индекс lo так, чтобы далее анализировать только элементы списка справа от срединного элемента (4) .
Поиск значения 33 в списке [3, 6, 14, 16, 33, 55, 56, 89] возвращает индекс 4.
Материал этого шага должен укрепить ваше общее понимание кода в том, что касается условного выполнения, основных ключевых слов и арифметических операций, а также важного вопроса доступа по индексу к последовательностям программным образом. Но что еще важнее, вы узнали, как упрощать решение сложных задач с помощью рекурсии.
На следующем шаге мы рассмотрим рекурсивный алгоритм быстрой сортировки.
