停止二進制搜索的證明

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，這是終止條件。