0

我正在为我的考试修改算法，我试图解决这个练习，但我想不出一个解决方案。

这是伪代码。

1. int search (int [] a, int x) {
2. // Pre: ∃i:Nat (0≤i<a.length ∧ a[i]=x) ∧ a is in ascending order
3. // Post: 0≤ r≤ a.length ∧
4. // ∀i:int.(0 ≤ i < r → a[i] < x) ∧ a[r]=x
5. int left, middle; int right = a.length;
6. if (a[0]>=x) return 0; else left=0; //a[left]<x (a)
7. while ((right-left>1){ (b)
8. // invariant: (I1) 0≤ left < right ≤ a.length ∧
9. // (I2) ∀i:int(0 ≤ i ≤ left → a[i] < x) ∧
10. // (I3) ∀i:int(right ≤ i < a.length → a[i] > x)
11. // (note: a[i]>x not a[i]≥x)
12. // Variant: right-left-1
13. middle = (left+right) / 2; // left < middle < right (*)
14. if ( a[middle]== x) return middle;
15. else {if a[middle)<x) left = middle ;
16. else right=middle;} (c)
17. }
18. } // left+1=right } (d)

因此，现在的代码不满足后置条件，因为对于某些输入（例如 x = 1 和 a={0,1,1,1,1}），第 14 行返回的值不满足第 4 行的后置条件。练习要求：“替换第 14 行的“return middle;”。通过 while 循环并返回代码，使其满足后置条件。包括足够强的变体和不变式以暗示返回时的后置条件. 提示：确保你包括说明没有改变的内容。

我一直无法找到解决方案。谁能帮我？

提前谢谢，VJ

编辑：好的，谢谢你们俩的帮助。

while(middle > 0 && a[middle] == x){
middle--;

} 返回中间；

我选择了中间的变体。并且不变量是：

0x

你认为这是正确的吗？

4

2 回答 2

0

当 a[middle] = x 我们确定我们应该返回 index middle 或它之前的东西，如果在 middle 之前有相同的值。

所以

if (a[middle]==x) {
    while (--middle>0 && a[middle]==x) {};
    return middle+1;
}

但这可能很慢，例如当整个 a 包含相同的值时，它具有线性时间复杂度。

于 2011-03-01T21:03:34.913 回答
0

Ajuc 发布了一个使用循环的解决方案，但正如他所说，这可能会很慢。

一种更快的方法是再次在左侧数组上使用二进制搜索。如果没有找到返回 i，否则返回这个二分查找的结果。复杂度将保持不变（O（logn））。

由于这看起来像家庭作业，我会让你自己弄清楚其余的:)。

于 2011-03-01T21:07:36.000 回答