Двоичный, или бинарный, поиск элемента в списке (метод деления пополам). Решение задачи на Python
Двоичный поиск, его же называют бинарным поиском – это алгоритм поиска элемента в отсортированном массиве. В случае с Python речь пойдет о поиске в списке. Найти элемент в списке – это значит, определить его порядковый номер, то есть индекс, то есть определить, где он находится. Или сделать вывод, есть искомый элемент в списке или его нет. Однако если это какая-то реальная подзадача, решаемая с помощью Питона, то искать элемент бинарным поиском наверное не надо. Есть методы списка, с их помощью проблема может решаться парой строчек кода. Задача двоичного поиска может иметь практическое значение для более низкоуровневых языков, например Си, и с точки зрения изучения алгоритмов. Почему поиск называют двоичным? Потому что сначала целый массив делится как бы пополам, потом отрезок массива также делится на две части и так далее. Еще раз обратим внимание, двоичный поиск работает для предварительно отсортированного массива. Допустим, в этом списке мы ищем число 31. Потребуются три переменные для хранения индексов начала, конца и середины отрезка, в котором происходит поиск. Сначала берется весь список. Поэтому нижней границе мы присваиваем индекс первого элемента, верхней – последнего (здесь 10 элементов, индекс последнего 9). Индекс середины находим, складывая индексы границ и деля нацело на 2. Если бы у нас было нечетное количество элементов, то какой-то один был бы точно посередине. Когда четное, за середину приходится брать либо этот элемент, либо этот. Определившись с границами, мы сравниваем заданное значение со значением середины. Если бы они совпали, мы прекратили бы поиск. Индекс середины и был бы индексом искомого элемента. Поскольку это не так, мы должны выполнить сравнения. Если искомое значение больше серединного, следует передвинуть нижнюю границу на одну позицию дальше от середины. И вычислить новую середину. В данном случае нижняя граница уйдет на позицию 5. А новая середина будет с индексом 7. Теперь сравниваем средний элемент уже этого отрезка с заданным значением. Здесь элемент середины больше, чем искомое число, поэтому сдвигаем уже верхнюю границу. И устанавливаем ее перед серединой. То есть если середина у нас имеет позицию 7, то верхняя граница будет установлена в 6. Снова вычисляем середину. Ей оказывается элемент с индексом 5. Число 27 меньше, чем 31. Поэтому сдвигаем нижнюю границу чуть дальше середины, то есть в позицию 6. Вычислив индекс середины и сравнив значение с искомым, находим позицию нужного элемента. Тот факт, что здесь совпали все индексы, это частный случай. Элемент мог обнаружиться раньше, когда границы еще не сомкнулись. Теперь посмотрим как все это выглядит на Python. Здесь уже подготовлен код, который формирует список из десяти случайных чисел. Сортирует его по возрастанию и выводит на экран. Также запрашивается искомое число. Надо написать код бинарного поиска. Обозначим индекс нижней границы через переменную low и присвоим ей индекс первого элемента списка. Верхняя граница – это длина списка минус единица. Это индекс последнего элемента. Чтобы найти средний индекс, сложим low и high и разделим на 2. Поиск будет происходить в цикле. Условием продолжения работы цикла является несовпадение искомого значения со значением середины исследуемого отрезка. Если значение больше серединного, то сдвигаем нижнюю границу за середину. Если значение меньше серединного, сдвигаем верхнюю границу до середины. Мы можем заменить второе условие на ветку else. Потому что варианта, когда элемент с индексом mid равен value, здесь все равно быть не может. Тело while тогда бы вообще не выполнялось, так как логическое выражение в заголовке возвращало бы ложь. После того, как произошел сдвиг той или иной границы, надо вычислить индекс новой середины. Цикл завершится, когда элемент с индексом mid совпадет с value. И mid как раз и будет индексом искомого элемента. Данная программа работает при условии, что пользователь всегда вводит элемент, который обязательно есть в списке. Если ввести элемент, которого нет, то произойдет зацикливание, потому что условие при while никогда не станет ложным. При этом верхняя граница окажется левее нижней. То есть границы как бы пересекутся. Например здесь, если бы было введено число 32, а оно больше чем 31, нижняя граница сместилась бы на 34, а верхняя осталась бы на 31. Поэтому еще одним условием окончания цикла должна быть проверка, что левая граница не больше правой. При этом выводить ID надо, только если value и значение по индексу mid совпадают. Иначе сообщать, что элемента нет. Текстовое описание решения задачи и исходный код программы: Больше задач: Приложение для андроид: Купить PDF-версию (100 задач):
