Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Понятие бинарного поиска

Бинарный поиск – метод нахождения решения на некотором отрезке путем деления отрезка пополам, определения принадлежности решения одной из половин. При каждой такой операции множество возможных ответов сокращается вдвое.

Данный метод часто называют двоичным поиском, а сам процесс – дихотомией. Сложность алгоритма – O(log N), где N – мощность множества возможных ответов.

Целочисленный бинарный поиск

Предположим, что определено следующее:

[a,b] – отрезок поиска решения

ans – существующее решение на [a,b]

less(x) – функция, соответствующая тому, что x меньше решения (x < ans)

Задача «Угадай число»

Формулировка

Некто загадал число от 1 до 100. Требуется отгадать загаданное число с помощью вопросов вида «Загаданное число больше числа X?».

Решение

Положим отрезок поиска решения [L, R] равным [1, 100], т.е. L=1 и R=100. Далее, перед каждым вопросом будем вычислять X как середину отрезка [L, R], т.е. X = (L+R) div 2. В случае ответа «Да» задача сводится к поиску решения на отрезке [X+1, R] и мы полагаем, что L = X+1. В случае ответа «Нет» поиск загаданного числа следует продолжить на отрезке [L, X], для чего полагаем, что R = X.

Описанные выше действия следует продолжать до тех пор, пока L < R. По завершению алгоритма мы найдем ответ (он равен L и R). Следует отметить, что мы выполним не более 7 вопросов, т.к. 27 > 100.

Реализация

Вещественный бинарный поиск

Вещественный бинарный поиск - бинарный поиск, при котором осуществляется поиск вещественного значения на некотором вещественном отрезке [L, R]. При этом предполагается не точный поиск решения, а поиск решения с некоторой абсолютной погрешностью ε. Здесь ε - максимальная допустимая разность между найденным и точным значением искомого решения. В отличии от целочисленного бинарного поиска процесс продолжается до тех пор, пока отрезок поиска не станет меньше либо равен ε, т.е. пока R-L > ε. Следующий пример демонстрирует данный процесс.

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Цикл с параметром (for)
 Цикл с предусловием (while)
 Цикл с постусловием (do ... while)
 НОД и НОК
 Бинарный поиск
 A. Сложность бинарного поиска
 B. POBEDA-2014
 C. Угадай число
 D. Ксерокопии
 E. Космическое поселение
 F. Стреляй!
 G. Вырубка леса
 H. Корень кубического уравнения
 I. Дипломы
 J. Кампус

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru