这个循环不变量及其非正式证明是否正确？ （CLRS 第三版练习 2-1-3）
Is this loop invariant and its informal proof correct? (CLRS 3rd ed. exercise 2-1-3)
给定以下线性搜索算法（将索引 1 称为元素数组中第一个元素的索引）：
found_idx = nil
for i = 1 to A.length
if A[i] == value
found_idx = i
return found_idx
end-if
end-for
found_idx
我想知道这个循环不变式是否正确：
“在 for 循环的每次迭代开始时，found_idx 是数组中以 i-1 结尾的索引，如果该值存在，则该值存在
这是我根据 CLRS 中的格式提出的对此循环不变式的非正式解释：
- 初始化：在第一次迭代前为真，因为 i = 1 且以 i-1 结尾的数组为空，因此 found_idx 为 nil。
- Maintenance：每次迭代后都是如此，因为在
i 的每个值处，检查 A[i] 并 then i 递增，这意味着在每次新迭代之前已经检查了直到 i-1 的所有元素。
- 终止：这在
i > A.length 时终止，这意味着直到并包括 A.length 的所有元素都已被检查。
我主要担心的是，引用以 i-1 结尾的索引感觉不正确，因为循环从 i 处的 1 开始，这是数组的第一个元素。换句话说，引用数组的子数组感觉很荒谬，其中子数组的结束索引小于数组的起始索引，而该子数组首先应该是子数组。这似乎暗示上面给出的循环不变量在循环的[=29=]非常第一次迭代之前实际上是假的。
想法？
由于循环提前终止，其不变量如下：
found_idx = nil && ∀k<i : A[k] ≠ value
&&之后的部分表示"All of A's elements at indexes below i are not equal to value"。
- 在进入循环之前，这完全正确
- 有条件的要么将
found_idx 保持在 nil，要么提前终止循环
- 当
i 达到 A.length 时循环终止
循环的post-条件是found_idx = nil && ∀k<A.length : A[k] ≠ value，这仅仅意味着value不在A的元素中。这也意味着您可以通过如下重写循环来消除 found_idx：
for i = 1 to A.length
if A[i] == value
return i
end-if
end-for
return nil
给定以下线性搜索算法（将索引 1 称为元素数组中第一个元素的索引）：
found_idx = nil
for i = 1 to A.length
if A[i] == value
found_idx = i
return found_idx
end-if
end-for
found_idx
我想知道这个循环不变式是否正确： “在 for 循环的每次迭代开始时，found_idx 是数组中以 i-1 结尾的索引，如果该值存在，则该值存在
这是我根据 CLRS 中的格式提出的对此循环不变式的非正式解释：
- 初始化：在第一次迭代前为真，因为 i = 1 且以 i-1 结尾的数组为空，因此 found_idx 为 nil。
- Maintenance：每次迭代后都是如此，因为在
i的每个值处，检查A[i]并 theni递增，这意味着在每次新迭代之前已经检查了直到i-1的所有元素。 - 终止：这在
i > A.length时终止，这意味着直到并包括A.length的所有元素都已被检查。
我主要担心的是，引用以 i-1 结尾的索引感觉不正确，因为循环从 i 处的 1 开始，这是数组的第一个元素。换句话说，引用数组的子数组感觉很荒谬，其中子数组的结束索引小于数组的起始索引，而该子数组首先应该是子数组。这似乎暗示上面给出的循环不变量在循环的[=29=]非常第一次迭代之前实际上是假的。
想法？
由于循环提前终止，其不变量如下：
found_idx = nil && ∀k<i : A[k] ≠ value
&&之后的部分表示"All of A's elements at indexes below i are not equal to value"。
- 在进入循环之前，这完全正确
- 有条件的要么将
found_idx保持在nil，要么提前终止循环 - 当
i达到A.length 时循环终止
循环的post-条件是found_idx = nil && ∀k<A.length : A[k] ≠ value，这仅仅意味着value不在A的元素中。这也意味着您可以通过如下重写循环来消除 found_idx：
for i = 1 to A.length
if A[i] == value
return i
end-if
end-for
return nil