这个循环不变量是否正确？

Question

线性搜索循环的伪代码：

for j = 1 to A.length 
   if(A[j] = v) 
      return j;
return NIL

我写的循环不变量：

在 for 循环的每次迭代开始时，j 是 A[j-1] 之后的下一个索引'等于 v。

初始化：

当j等于1之前检查是否小于A.length，之前的索引是0。那么 A[0] 不等于 v，因为在这种情况下 A[0]甚至不存在。

维护：

如果 A[j] 等于 v 则循环终止。这意味着我们没有下一次迭代。但是，如果它不等于 v，那么循环的下一次迭代将在保留循环不变性的情况下执行。

终止：

导致for循环终止的条件是j大于A.length或 v 等于 A[j]。因为每次循环迭代都会将 j 增加 1，我们已经根据 [=31] 检查了 A 的每个元素=]v 直到 j 大于 A.length。因此算法是正确的。如果 v 等于 A[j] 那么这意味着我们已经找到了我们一直在搜索的元素。因此该算法是正确的。

这些正确吗？

Answer 1

还不错，但你可以做一些改进。

循环不变式："next after where..."语言笨拙，你没有用它来证明算法正确，所以没有理由维护它。像这样会更好："At the start of each iteration, there does not exist any i < j such that A[i] == v".

维护：如果A[j] != v，循环继续。因为不存在任何i < j使得A[i] == v，并且A[j]!=v，那么有也不存在任何 i <= j 使得 A[i] == v，并且循环不变量对下一个更大的 j 值成立。

然后你可以在终止条件中使用它：如果在数组中找到 v 并且 returns 它的索引，循环会提前终止。否则，循环不变量对于 j == length+1 成立，并且已知不存在任何 i <= length 使得 A[i]==v，即 v 不出现在数组中。

这个循环不变量是否正确？

Is this loop invariant correct?

algorithm

loop-invariant