Сможете ли вы ответить, сколько попыток нужно, чтобы угадать число в диапазоне от 1 до 1000? При условии, что тот, кто загадал число, будет говорить вам при названии очередного числа "больше", "меньше" или "равно".
И снова, здравствуйте! Я решил изучить алгоритмы в программировании. Некоторые алгоритмы я буду записывать в свой блог.
Сегодня мы с вами изучаем алгоритм бинарный поиск.
Предположим, что у вас есть упорядоченный список каких-то значений. Это может быть, например, числа от 1 до 100. Или телефонный справочник, в котором фамилии абонентов упорядочены по алфавиту. Каким образом найти какое-либо значение из этого списка?
Самый простой способ, который приходит вам в голову - это начать перебирать с начала или с конца. Это называется прямым поиском, более удачное название "тупой" поиск. Он тупой, потому что если допустим, вам надо найти число 99, а перебираете вы, начиная с единицы, у вас уйдет 99 попыток.
Другим, более удачным способом поиска значения в упорядоченном списке является бинарный поиск.
При этом способе поиска, вы сразу делите список на 2. Затем проверяете, в какой половине списка лежит искомое значение. Таким образом, уже после первой попытки вы сразу же откинули половину списка.
Подобным же образом, вы каждый раз делите список на 2 и проверяете, в какой половине списка лежит ваше значение.
На вышеприведенной картинке указан ответ на вопрос в начале поста. Как мы видим, для того, чтобы найти загаданное число в диапазоне от 1 до 1000 нужно не более 10 попыток, при условии использования алгоритма "бинарный поиск".
Задания на дом:
1. Сколько попыток нужно, чтобы найти загаданное число в диапазоне от 1 до 100?
2. На сколько попыток увеличится поиск результата, если чисел будет не 100, а 200?
Ответы пишите в комментариях!
