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行目の事後条件：演習では、次のように求めています。 。ヒント：何が変わらないかを述べるために含めるようにしてください。」

私は解決策を見つけることができませんでした。誰か助けてもらえますか？

よろしくお願いします、VJ

編集：わかりました、あなたの助けてくれてありがとう。

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

}真ん中を返す;

バリアントをミドルに選択しました。そして不変である：

0x

これは正しいと思いますか？

4

2 に答える 2

0

Ajuc はループを使用したソリューションを投稿しましたが、彼が言ったように、これは遅くなる可能性があります。

より高速なアプローチは、左側の配列で二分探索を再度使用することです。見つからない場合は i を返し、そうでない場合はこの二分探索の結果を返します。複雑さは変わりません (O(logn))。

これは宿題のように見えるので、残りは自分で考えさせます:)。

于 2011-03-01T21:07:36.000 に答える
0

a[middle] = x の場合、middle の前に同じ値がある場合は、必ず index middle またはその前の何かを返す必要があります。

そう

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

しかし、それは遅くなる可能性があります。たとえば、 a 全体に同じ値が含まれている場合、線形時間の複雑さがあります。

于 2011-03-01T21:03:34.913 に答える