二进制排序：如果列表[中] ==关键案例

Question

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

这是伪代码。

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行中，通过一个while循环并返回 代码，以便它满足后置条件。和 不变的强度足以暗示 返回条件。提示：确保你包括说明什么不会改变。“

我一直没有找到解决办法。 任何人都可以帮助我吗？

由于提前， VJ

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

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

} return middle;

我选择变体为中间。而不变的是：

0X

。你认为这是正确的？

Answer 1

当[middle] = x时，如果在中间值之前有相同的值，我们相信我们应该返回索引中间或之前的东西。

所以

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

但是，当整个一个包含它具有线性时间复杂度相同的值，可以是缓慢的，例如。

Answer 2

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

更快的方法是在左侧阵列上再次使用二进制搜索。如果找不到则返回i，否则返回此二进制搜索的结果。复杂性将保持不变（O（logn））。

由于这看起来像功课，我会让你自己找出其余的:)。