Комбинаторные алгоритмы для программистов



             

Бинарный поиск - часть 2


Это утверждение очевидно первый раз, когда мы входим в цикл при
l = 1
и
h = n
, и непосредственно по индукции проверяется, что оно выполняется при каждом проходе через цикл. Когда мы выходим из цикла, то должно быть
l > h
, и поэтому утверждение принимает вид
z \notin \{ x_1,\ldots,x_{l - 1} \}
и
z \notin \{ x_{h + 1},\ldots,x_n \}
, откуда следует, что
z \notin \{ x_1,\ldots,x_n \}
.




Содержание  Назад  Вперед