我如何使用霍尔逻辑证明这种二进制搜索算法是正确的？

Question

这是算法：

// Precondition: n > 0

l = -1;
r = n;

while (l+1 != r) {
    m = (l+r)/2;

    // I && m == (l+r)/2

    if (a[m] <= x) {
        l = m;
    } else {
        r = m;
    }
}
// Postcondition: -1 <= l < n

我做了一些研究并将不变量缩小到 if x is in a[0 .. n-1] then a[l] <= x < a[r]。

虽然我不知道如何从那里取得进步。前提条件似乎过于宽泛，所以我无法证明 P -> I.

非常感谢任何帮助。这些是可以用来证明算法正确性的逻辑规则：

Answer 1

不变量是

-1 <= l and l + 1 < r <= n and a[l] <= x < a[r]

使用隐式约定 a[-1] = -∞、a[n] = +∞。

然后在if声明

a[l] <= x < a[r] and a[m] <= x implies a[m] <= x < a[r]

和

a[l] <= x < a[r] and x < a[m] implies a[l] <= x < a[m].

在任何一种情况下，分配都会建立 a[l] <= x < a[r]。

同时-1 <= l and l + 1 < r <= n保证了-1 < m < n，这样a[m]的评价就可以了

终止时，l + 1 = r 并由不变量

-1 <= l < n and a[l] <= x < a[l + 1].

我如何使用霍尔逻辑证明这种二进制搜索算法是正确的？

How can I prove this binary search algorithm is correct using hoare logic?

algorithm

binary-search

correctness

proof-of-correctness

hoare-logic