Написать функцию, binsearch(x, A), реализующую двоичный поиск элемента x по индексируемой последовательности (списку, кортежу или даже range) A. Гарантировано, что последовательность упорядочена по возрастанию. Функция возвращает True, если $$ x \in A $$ и False в противном случае.
print(binsearch(123, sorted([123, 12, 45, 67, 23, 678, 12345, 4, 23, 768])))
- Совет: при делении пополам, особенно отрезков нечётной длины, не запутайтесь в маленьких отрезках!
- Не создавайте новых подпоследовательностей большой длины. Для того, чтобы сделать половину списка из миллиона элементов, надо скопировать полмиллиона значений. Если делать это в цикле, программа закончится нескоро…
True
- Знакомые с рекурсией могут написать рекурсивную функцию (ей тут самое место!), но это необязательно
Задача похожа на ../Homework_ManualLogarithm, и даже слегка проще неё ☺
Cпойлер: