Бинарный поиск: Пример
Представим ситуацию:
Вы с другом решили сыграть в игру. Один из вас загадывает число от 1 до 100, другой - отгадывает. После догадки загадывающий обязан подсказывать его число больше или меньше.
___
Было загадано число 98.
Если использовать простой перебор (1, 2, 3...), потребуется 98 догадок. Не самые радужные перспективы. Воспользуемся бинарным поиском.
Происходит следующий диалог:
О - отгадывающий, З - загадывающий
О: (В уме делит пополам диапазон от 1 до 100) - 50
З: больше
О: (Откидывает все что было до 50. В уме делит пополам диапазон от 51 до 100) - 75
З: больше
О: (Откидывает все что было до 75. В уме делит пополам диапазон от 76 до 100) - 88
З: больше
О: (Откидывает все что было до 88. В уме делит пополам диапазон от 89 до 100) - 94
З: больше
О: (Откидывает все что было до 94. В уме делит пополам диапазон от 95 до 100) - 97
З: больше
О: (Откидывает все что было до 97. В уме делит пополам диапазон от 98 до 100) - 99
З: меньше
О: (Откидывает все что было после 98. Остается диапазон от 98 до 98) - 98
З: верно!
Я специально взял число(98), которое попадет в диапазон худшего случая. Теперь мы наглядно видим, что:
Для того, чтобы найти число в диапазоне от 1 до 100, в худшем случае необходимо сделать 7 догадок.
Надеюсь, принцип работы бинарного поиска понятен, переходим к школьной программе
___
course_intro
