Бинарный поиск - часть 2
Это утверждение очевидно первый раз, когда мы входим в цикл при
и
, и непосредственно по индукции проверяется, что оно выполняется при каждом проходе через цикл. Когда мы выходим из цикла, то должно быть
, и поэтому утверждение принимает вид
и
, откуда следует, что
.
Содержание Назад Вперед