<TOGGLE>text</TOGGLE>

На примере списка стоп-слов сравним метод перебора и бинарный поиск. Первое заметное отличие — бинарный поиск сложнее в реализации. В нашем случае сортировка метода перебора занимает 8 строк, а бинарный поиск — 18 строк. Стоит ли писать такие сложные программы? Да, если мы ищем по массиву из ста элементов и более.

Если нужно искать в небольших массивах, можно использовать метод перебора — он будет работать со сравнимой скоростью или даже быстрее.

Второе важное ограничение бинарного поиска — массив всегда должен быть упорядоченным. Со стоп-словами это ограничение не мешало, потому что это фиксированный список, который надо подготовить всего один раз.

Но если список не фиксированный и надо добавлять слова во время работы программы, тогда придется писать дополнительный сложный код. Мы не можем просто добавлять слова в конец массива, потому что это нарушит порядок.

И третье ограничение — некоторые данные просто нельзя упорядочить. Например, не существует какого-то естественного общепризнанного способа упорядочить цвета:

Цвета Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел:

• Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д.
• Самый северный — Певек, координаты 69°42′ с. ш. 170°19′ в. д.

Какие координаты больше? Если бы речь шла только о широте или долготе, мы бы без труда ответили. Но здесь пара чисел: при сравнении широта может оказаться больше, а долгота меньше. Нельзя сказать, что широта важнее долготы или наоборот. Поэтому у координат и других пар чисел нет какого-то естественного и очевидного порядка.

При этом всегда можно сравнить два цвета или две координаты и узнать, совпадают они или нет. Для таких данных будет работать метод перебора, которому достаточно проверки на равенство. Бинарный поиск не сработает, потому что ему нужно, чтобы данные были больше или меньше.

Бинарный поиск быстрее метода перебора, но пока не обсудили, насколько именно он быстрее. Один из способов сравнить производительность на практике — написать программы и измерить время их выполнения.

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

Сравним время поиска на массивах из 10, 1 000 и 1 000 000 элементов.

Что будем сравнивать? В обоих алгоритмах есть цикл. В одном случае он может выполняться 100 раз, а в другом — 50. Это значит, что второй цикл в два раза быстрее первого, хотя мы и не можем назвать точное время в секундах.

Проблема в том, что на разных данных количество циклов будет разным.

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

Лучшим для бинарного поиска также окажется один цикл. В худшем случае бинарный поиск пройдет четыре цикла:

• Первый поиск — целый массив из 10 элементов
• Второй — подмассив из пяти элементов
• Третий — подмассив из двух элементов
• Четвертый — подмассив с одним последним элементом

В итоге среднее число циклов для бинарного поиска — 2.

Сведем результаты в одну таблицу:

Как видим, разница в производительности колоссальная, особенно на больших массивах.

• В уроке мы рассмотрели два алгоритма: метод перебора и бинарный поиск
• У метода перебора есть два варианта: Простой перебор, чтобы проверить, есть ли элемент в списке

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ

130

курсов

1000

упражнений

2000

часов теории

3200

тестов