Грокаем а Иллюстрированное пособие для программистов и любопытствующих

А если догадка была слишком велика, то обновляется переменная high. Полный код выглядит гак:

В переменных low и high хранятся границы
def binary_search(list, item): ■* той части списка, в которой выполняется

low = 0/// high = len(list)-l **'"		поиск
while low <= high:	-<	Пока эта часть не сократится до одного элемента ..
mid = (low + high)	<	... проверяем средний элемент
guess = listfmid]
if guess == item:	-<	Значение найдено
return mid
if guess > item:	■<	Много
high = mid - 1
else:	•4	Мало
low = mid + 1
return None		Значение не существует
r_list = [1, 3, 5, 7, 9]	<	А теперь протестируем функцию! Вспомните: нумерация элементов на-

print binary_search(my_list, 3) # => 1 ■*"" чинается с 0. Второй ячейке соответ-
print binary_search(my_list, -1) # => None^ ствуетиндекс 1





"None" в Python означает "ничто". Это признак того, что элемент не найден
Упражнения
1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем зна­чение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?
1.2 Предположим, размер списка увеличился вдвое. Как изменится мак­симальное количество проверок?
Время выполнения
Каждый раз, когда мы будем рассматривать очередной алгоритм, я буду обсуждать время его выполнения. Обычно следует выбирать самый эффек­тивный алгоритм, будь то оптимизация по времени или памяти.
Вернемся к бинарному поиску. Сколько времени сэкономит его приме­нение? В первом варианте мы последовательно проверяли каждое число, одно за другим. Если список состоит из 100 чисел, может потребоваться до 100 попыток. Для списка из 4 миллиардов чисел потребуется до 4 миллиар­дов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным.
С
ПРОСТОЯ
поиск


100 ЭЛЕМЕНТОВ
4
100 попыток


4 000 000 ЭЛЕМЕНТ


1 попыток


4 000 000 000
ЭЛЕМЕНТОВ


ЛИНЕЙНОЕ
6 РЕМ Л


ы попытки


БИНАРНЫЙ
ПОИСК



4*
4 000 000 000
попыток
Время выполнения алгоритмов поиска


м
^v ЛОГАРИФМИЧЕСКОЕ В РЕМ л

бинарным поиском дело обстоит иначе. Если список состоит из 100 эле­ментов, потребуется не более 7 попыток. Для списка из 4 миллиардов эле­ментов потребуется не более 32 попыток. Впечатляет, верно? Бинарный поиск выполняется за логарифмическое время. В следующей таблице при­водится краткая сводка результатов.
«Обол ьшое»
С пециальная нотация «О-большое» опи­сывает скорость работы алгоритма. Зачем вам это? Время от времени вам придется использовать чужие алгоритмы, а пото­му неплохо было бы понимать, насколь­ко быстро или медленно они работают. В этом разделе я объясню, что представ­ляет собой «О-большое», и приведу спи­сок самых распространенных вариантов времени выполнения для некоторых ал­горитмов.
Время выполнения алгоритмов растет с разной скоростью
Боб пишет алгоритм поиска для NASA. Его алгоритм заработает, когда ра­кета будет подлетать к Луне, и поможет вычислить точку посадки.
Это один из примеров того, как время выполнения двух алгоритмов растет с разной скоростью. Боб пытается выбрать между простым и бинарным поиском. Его алгоритм должен работать быстро и правильно. С одной стороны, бинарный поиск работает быстрее. У Боба есть всего 10 секунд, чтобы выбрать место посадки; если он не уложится в это время, то момент для посадки будет упущен. С другой стороны, простой поиск пишется про­ще и вероятность ошибок в нем ниже... Конечно, Боб совершенно не хочет допустить ошибку в коде посадки ракеты. И тогда для пущей уверенности Боб решает измерить время выполнения обоих алгоритмов для списка из 100 элементов.
Допустим, проверка одного элемента занимает 1 миллисекунду (мс). При простом поиске Бобу придется проверить 100 элементов, поэтому поиск займет 100 мс. С другой стороны, при бинарном поиске достаточно прове­рить всего 7 элементов (log₂100 равен приблизительно 7), а поиск займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения простого поиска? А при бинарном поиске? Обязательно ответьте на оба вопроса, прежде чем продолжить чтение.
В
ПРОСТОЯ поиск
ioo мс


БИНАРНЫЙ поиск
7 МС

ремя выполнения простого и бинарного поиска для списка из 100 элементов
Боб проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс (log₂l 000 000 000 равен приблизительно 30). «32 мс! — думает Боб. — Бинарный поиск в 15 раз быстрее простого, потому что простой поиск для 100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой поиск займет 30 х 15 = 450 мс, верно? Гораздо меньше отведенных 10 се­кунд». И Боб выбирает простой поиск. Верен ли его выбор?
Нет, Боб ошибается. Глубоко ошибается. Время выполнения для простого поиска с 1 миллиардом элементов составит 1 миллиард миллисекунд, а это 11 дней! Проблема в том, что время выполнения для бинарного и простого поиска растет с разной скоростью.

ПРОСТОЯ поиск			БИНАРНЫЙ ПОИСК
100 ЭЛЕМЕНТОВ	юо МС	7 МС
10 000 ЭЛЕМЕНТОВ	to секунд	14 мс
1 000 000 ЭЛЕМЕНТОВ	11 дней	32 МС

Время выполнения растет с совершенно разной скоростью!





Другими словами, с увеличением количества элементов бинарный поиск занимает чуть больше времени. А простой поиск займет гораздо больше времени. Таким образом, с увеличением списка бинарный список внезап­но начинает работать гораздо быстрее простого. Боб думал, что бинарный
поиск работает в 15 раз быстрее простого, но это не так. Если список со­стоит из 1 миллиарда элементов, бинарный поиск работает приблизитель­но в 33 миллиона раз быстрее. Вот почему недостаточно знать, сколько времени должен работать алгоритм, — необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь-то вам и пригодится «О-большое».
« О-большое» описывает, насколько быстро работает алгоритм. Предположим, имеется список размера п. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить п операций. Время выполнения «О-большое» имеет вид О(п). Постойте, но где же секунды? А их здесь нет — «О-большое» не сообщает скорость в секундах, а позволяет сравнить количе­ство операций. Оно указывает, насколько быстро возрастает время выполнения ал­горитма.
А теперь другой пример. Для проверки списка размером п бинарному поис­ку потребуется log п операций. Как будет выглядеть «О-большое»? 0(log п). В общем случае «О-большое» выглядит так:
Осп)
«О-БОЛЬШОЕ» А*. КОЛИЧЕСТВО
ОПЕРАЦИЙ
Как записывается «О-большое»
Такая запись сообщает количество операций, которые придется выпол­нить алгоритму. Она называется «О-большое», потому что перед количе­ством операций ставится символ «О» (а большое — потому что в верхнем регистре).
Теперь рассмотрим несколько примеров. Попробуйте самостоятельно оце­нить время выполнения этих алгоритмов.
Наглядное представление «О-большое»
Ч
Как должен выглядеть хороший алгоритм для построения этой сетки?


тобы повторить следующий практический пример, достаточно иметь не­сколько листков бумаги и карандаш. Допустим, вы должны построить сетку из 16 квадратов.
Алгоритм 1
К
ак вариант можно нарисовать 16 квадратов, по одному за раз. Напо­минаю: «О-большое» подсчитывает количество операций. В данном при­мере рисование квадрата считается одной операцией. Нужно нарисовать 16 квадратов. Сколько операций по рисованию одного квадрата придется выполнить?
Чтобы нарисовать 16 квадратов, потребуется 16 шагов. Как выглядит время выполнения этого алгоритма?
Алгоритм 2
А
теперь попробуем иначе. Сложите лист пополам.
На этот раз операцией считается сложение листка. Получается, что одна операция создает сразу два прямоугольника!
С
ложите бумагу еще раз, а потом еще и еще.
Р
1 СЛОЖЕНИЕ