Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
А это ссылки для вас из моего канала
Двоичный поиск в упорядоченном списке (Python)
Поиск это всегда актуально в программировании. Поиск в списке довольно прост. Мы просто перебираем элементы один за другим и сравниваем с искомым значением. У списка есть и свои методы для поиска. Но если список достаточно длинен то это может потребовать времени. Ведь это время пропорционально длине списка.
Другое дело, когда список отсортирован. Тогда можно применить какую либо разновидность двоичного (бинарного) поиска. В чём заключается двоичный поиск?
- Находим элемент в середине списка. Для этого делим нацело на 2 сумму первого и последнего индекса списка.
- Если искомое значение равно элементу списке по середине, то поиск закончен.
- Сравним искомое значение с элементов на середине. Если искомое значение меньше, то выбираем для поиска первую (левую) половину списка, иначе вторую.
- Переходим к пункту 1.
Ниже представлена программа, осуществляющая поиск по описанному выше словесному алгоритму. Поиск осуществляется функцией search().
Сделаем ряд замечаний по поводу представленной программы.
Замечание 1
Мы видим, что предварительно список был отсортирован. Можно возразить, что сортировать список для поиска может быть накладно. Однако речь идёт несколько о другом. Если хранить данные в изначально упорядоченном виде и сохранять порядок в случае добавления элемента, то двоичный поиск даст существенное преимущество по отношению к линейному поиску.
Замечание 2.
Если в списке несколько одинаковых элементов, то найдя один из таких элементов мы легко найдём все остальные, так как они все расположены рядом.
Ниже представлен несколько усовершенствованный алгоритм двоичного поиска.
Представленная программа ищет не только точное совпадение в списке, но если элемента в списке нет, она указывает, где бы мог располагаться искомый элемент.
Несколько пояснений к программе.
- n это искомый элемент
- Данная программа (функция search2()) учитывает, что элемент может отсутствовать в списке. По результату работы функции легко понять, где мог бы находиться искомый элемент списка, если его там нет.
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.