algorithm - 停止二分搜索证明

Question

l = -1; u = n;
while l+1 != u
    m = l + (u-l)/2;
    if x[m] < t
        l = m;
    else
        u = m;
p = u;
if p >= n || x[p] != t
     p = -1;

在上面的代码中，我们假设 x[-1] < t 和 x[n] >= t 和 n >= 0。上面的代码是一个修改过的二分查找，它可以返回整数数组 x[0..n-1] 中第一次出现的整数t，而不是返回一个随机的。

我的问题是这样的：

为什么上面的代码总是停止？任何人都可以解释或证明吗？

谢谢，

Answer 1

因为在每次迭代中，在整数运算的约束范围内，两者之间l的差距减半。u所有（正）整数减半的序列最终都必须达到 1，这是终止条件。