这是这个循环的正确不变式吗？

Question

这是数组中线性搜索的伪代码，return如果在数组 A 中找到所需的元素 e，则索引 i，NIL 否则（这是来自 CLRS 书，第 3 版，练习 2.1-3）：

LINEAR_SEARCH (A, e)
    for i = 1 to A.length
        if A[i] == e
            return i
    return NIL

我试图从中推断出一个循环不变性，所以根据我的理解，我认为一个是这样一个事实，即在循环中的任何给定时刻，子数组 A[1..i-1] 只包含相等性测试证明错误的值。

具体来说，在第一次迭代之前i-1 == 0，这意味着子数组的长度为空，因此不可能有属于它的元素v使得v == e。在任何下一次迭代之前，作为退出条件的相等性测试，假设的不变量属性必须仍然成立，否则循环已经结束。在终止时，要么函数即将 return 一个索引（在这种情况下循环不变量是平凡真实的），要么 NIL 是 returned（在这种情况下 i == A.length + 1 ，因此循环不变量对任何 1 < j < i).

都成立

以上是否正确？你能提供一个正确的循环不变式以防万一吗？

感谢您的关注。

Answer 1

循环不变性：在 for 循环的每次迭代开始时，我们对所有 j < i.
初始化：在第一次循环迭代之前，不变量成立，因为数组是空的。
维护：循环不变量在每次迭代中都被维护，否则在第 i 次迭代中有一些 j < i 这样 A[j] == e。但是，在这种情况下，对于循环的第 j 次迭代，返回值 j，并且没有循环的第 i 次迭代，这是一个矛盾。
Termination循环终止时，可能有两种情况：一种是i <= A.length次迭代后终止，returns i，在这种情况下 if 条件确保 A[i] == e。另一种情况是 i 超过 A.length，在这种情况下，通过循环不变量，对于所有 j <= A.length、A[j] != e，返回 NIL 是正确的。

这是这个循环的正确不变式吗？

Is this a correct invariant for this loop?

algorithm

loops

clrs

loop-invariant