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] 中 first 出现的整数 t 而不是返回随机数一。

我的问题是这样的:

为什么上面的代码总是卡顿？谁能解释或证明？

谢谢，

Answer 1

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