Упражнение 21: Бинарный поиск

Оригинал: Exercise 21: Binary Search

Переводчик: Феликс Ло

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

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

Если мы хотим найти число (X) в отсортированном списке чисел, мы будем выполнять следующие действия:

• Получаем среднее значение списка ((M)) и сравниваем его с (X).
• Если (X = M), вы закончили.
• Если (X > M), продолжайте поиск в диапазоне от (M + 1) до конца списка.
• Если (X < M), продолжайте поиск в диапазоне от начала списка до (M - 1).
• Повторите это до тех пор, пока не будет найдено (X) или диапазон не станет пустым.

Этот алгоритм применим ко всему, что можно сравнить на равенство. Он работает со строками, числами и любыми другими объектами, которые можно отсортировать.

Частично руководящие упражненияВаш BSTree уже имеет операцию get, которая похожа на бинарный поиск. Разница заключается в том, что BSTree уже разделён, поэтому нет необходимости повторять это. В этом упражнении вы реализуете бинарный поиск для DoubleLinkedList и Python list и сравните производительность с BSTree.get. Вашей целью является изучение следующего:+ Для простого поиска элемента, какова эффективность BSTree по сравнению с Python list?

• Как плохо работает бинарный поиск для DoubleLinkedList?
• Будут ли патологические случаи для BSTree также влиять на производительность бинарного поиска для list?

При анализе производительности не включайте время, затраченное на сортировку чисел. Это важно при глобальной оптимизации, но здесь нас интересует скорость работы алгоритма бинарного поиска. Вы можете использовать встроенный алгоритм сортировки Python для сортировки list, так как это не является основной задачей. Этот урок полностью посвящен скорости поиска между тремя типами структур данных.## Исследовательское обучение
Определите максимальное количество сравнений, которое может потребоваться алгоритму. Сначала попробуйте самостоятельно понять это, а затем исследуйте алгоритм, чтобы найти истинный ответ. После этого запомните этот истинный ответ.
Может ли любой из этих оптимизаций быть применён к сортировочному алгоритму?
Попробуйте визуализировать, что делает алгоритм в каждом из данных структур данных. Например, в DoubleLinkedList вы можете почти представить себе процесс перемещения вперед и назад до тех пор, пока не будет найдено решение.
Чтобы дать себе дополнительный вызов, попробуйте сделать DoubleLinkedList отсортированным списком, где каждое вставление всегда происходит на правильное место после сортировки. Теперь напишите анализ производительности, включая добавление элементов и сортировку списка чисел, чтобы лучше понять, как можно повысить общую производительность.

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