Бинарный поиск - часть 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 \}$