Двоичный поиск и его границы
Двоичный поиск требует упорядоченных данных и понятного правила сравнения.
В этом занятии
- Самостоятельно решить задачу по теме «Двоичный поиск и его границы» и объяснить проверку результата.
- Миссия «Половина карты»: придумай упорядоченный набор из 15 чисел и нарисуй, как сужается поиск одного числа и отсутствующего значения.
Пригодится: informatics11-extremum-sort
Разберёмся перед практикой+
Двоичный поиск и его границы
Двоичный поиск требует упорядоченных данных и понятного правила сравнения. Он проверяет середину текущего отрезка и отбрасывает половину, где искомое значение находиться не может. Без сортировки этот вывод неверен.
Для воспроизводимой трассировки фиксируют индексацию, включение границ и способ выбора середины. При повторах обычный алгоритм может найти любое вхождение; поиск первого требует дополнительного условия. Малое число сравнений не отменяет стоимость предварительной сортировки.
В [2,4,6,8,10] ищем 8: индексы 0..4, mid=(0+4)//2=2, значение 6. Далее 3..4, mid=3 и значение 8 найдено за два сравнения.
- Проверь сортировку и правила границ.
- После сравнения исключи уже проверенную середину и невозможную половину.
Открываем цифровую мастерскую…
Попробуйте самостоятельно
Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Миссия «Половина карты»: придумай упорядоченный набор из 15 чисел и нарисуй, как сужается поиск одного числа и отсутствующего значения.
- Сначала предположите результат, затем проверьте и объясните, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.