2

セクション 9.3 で、Job Bentley は修正された二分探索を提示します。

9.3 に示されている典型的な実装とより良いアプローチの短い抜粋

if (arr[mid] < key) low = mid+1
else if (arr[mid] > key) high = mid-1
else return mid;

異なる不変式との修正された/効率的な比較..

if (arr[mid] < key) low = m;
else high = m;

ループの外側では、キーがインデックス 'high' にあるかどうかがチェックされます。変更された二分探索では、左側のインデックス 'low' は (0 ではなく) -1 で始まり、'high' インデックスは (n-1 ではなく) n で始まり、ループが実行されます。

while (low + 1 != high)

この変更された検索は、low = 0 および high = n-1 に設定しても機能するようです。

しかし、Job Bentley のコードを推測するのは避けたいと思います。では、なぜ彼は low を -1 に、high を n に設定しているのでしょうか? これだけが機能するコーナーケースはありますか?

4

1 に答える 1

2

空 ( n == 0) の配列がある場合、) のチェックは、とで始まるwhile(low + 1 != high場合にのみ正しく終了します。low-1high0

while((-1 + 1) != 0) //true

代わりにlow開始した場合、または開始した場合(または両方)、ループは少なくとも 1 つのチェックを明確に実行します。0high-1

  • while((0 + 1) != 0) // false
  • while((-1 + 1) != -1) // false
  • while((0 + 1) != -1) // false

空の配列に対するその 1 つのチェックは、未定義の動作を引き起こす範囲外のインデックスにアクセスする可能性があります。

于 2015-06-20T15:00:13.250 に答える