0

二分探索アルゴリズムでは、上限要素はarray.length-1です。配列の最後の要素を見つけるにはどうすればよいですか？

長さ8の配列の要素の下限と上限がそれぞれ6と7の場合、私の中間要素は次のようになります。

mid =（6 + 7）/ 2、つまりJavaでは6

4

5 に答える 5

5

それは本当に正しい選択された中点と比較して正しいものを使用することに帰着します。たとえば（変数型宣言なし）、

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right)/2;
    if(a[mid] < val)
        return binsearch(a,val,mid+1,right);
    else
        return binsearch(a,val,left,mid);
}

valに一致する左端の要素のインデックスを提供します（配列の右端の要素であっても）。組み込みの整数切り捨てを使用するのではなく、最後の2つを明示的にチェックしたり切り上げたりする必要はありません。

ただし、valに等しい右端の要素のインデックスが必要な場合は、<演算子を>に変更する必要があり、midは次の式で指定する必要があります。

mid = (left+right+1)/2;

それはそれと同じくらい簡単です。

編集：もう1つ、これに使用するコードを調べたところ、binsearchの呼び出しも変更して、右端の要素に到達する必要があることに気付きました。このための完全なコードを投稿します（最初に行うべきでした）。これは、valに等しい右端の要素を見つけるための二分探索です。

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right+1)/2;
    if(a[mid] > val)
        return binsearch(a,val,left,mid-1);
    else
        return binsearch(a,val,mid,right);
}
于 2010-02-14T07:01:44.527 に答える
2

最も簡単なアプローチは、ハーフオープンレンジを使用することです。このように、下限は配列内の最後の有効なアイテムの1ステップ後になりますが、下限は最初のアイテムを直接指します。ただし、検索中は、範囲を包括的として扱います。範囲外の上限は、有効な「一致が見つかりません」の結果です。

各反復の開始時に、次のようになります...

lower <= target <= upper

「ターゲット」とは、検出されて返されるインデックスを意味します。

midは「（上+下）/2」として計算します。これは切り捨てられるため、midがupperと同じになることはありません。これは重要です。「upper」は範囲外である可能性があるため、「array[upper]」を法的に評価することはできません。

キー以上の最初のアイテムを見つけるには...

if array[mid] >= k :  lower <= target <= mid
if array[mid] <  k :  mid+1 <= target <= upper

キーよりも大きい最初のアイテムを見つけるには...

if array[mid] >  k :  lower <= target <= mid
if array[mid] <= k :  mid+1 <= target <= upper

これらのサブ範囲は包括的であり、正確に一致する必要がありますが、重複してはなりません。中央で単一のアイテムがオーバーラップすると（簡単な間違い）、無限ループが発生します。これが、1つのサブ範囲にmid+1を使用する理由の一部です。

2つの検索間で変更されるのは、比較演算子だけであることに注意してください。

last-less-or-equalを見つけるには、first-greaterを見つけて、結果から1を引きます。配列内のすべての項目がキーより大きい場合、-1を取得できます。

注-各反復でmidに対してのみキーをテストし（下限と上限がすでに正しいことがわかっています）、条件付きテストを1回だけ実行します。

ループの外側で、範囲外チェックと同等性チェック（必要な場合）を実行します。

int find_first_ge (int key)
{
  int lower = 0;
  int upper = array.length;

  while (upper > lower)
  {
    int mid = (lower + upper) / 2;

    if (array [mid] >= key)  //  for find_first_gt, use ">" here
    {
      upper = mid;
    }
    else
    {
      lower = mid + 1;
    }
  }

  return lower;
}

ノート

これを修正するために意図されたものと同じように無限ループのままにしたいくつかの間違いを修正するために編集されました。

秘訣は、二等分されたサブレンジが各キーテストの後に必要に応じて正確になり、常に元のフルレンジよりも少なくとも1つ小さいことを確認することです。自信過剰とメモリ不足により、それが私が何とか間違えたのです。上記は、頻繁に使用されるライブラリ（マルチウェイツリーライブラリのノード内で検索）で実際に機能するコードに基づいているため、間違っていると大きな問題が発生します;-)

ノート

言葉遣いを改善し、サブレンジ境界の説明を簡素化するために再度編集されました（範囲は半分開いていますが、包括的として扱われることに注意してください）。

于 2010-02-14T06:43:08.300 に答える
0

毎回切り上げることができます。

（6 + 7）/2.0 == 6.5

切り上げると7が出てきます。

または、中点に1つ追加することもできます。

ミッド=（6 + 7）/ 2 + 1

もう1つの方法は、次の再帰のために開始点または終了点を+1または-1に変更することです。これは、この主題に関するウィキペディアの記事がいくつかの実装で示しているものです。

min = mid + 1

また

max = mid-1

于 2010-02-14T06:14:20.790 に答える
0

下限と上限が互いに範囲内にある場合は、両方を確認してください。

于 2010-02-14T06:19:32.787 に答える
0

二分探索は、正確に正しく行うのが難しいことで有名です。プログラミングパールには、さまざまな問題とエッジケースに関する非常に徹底的な分析があり、正しい実装があります。これは、すべてのプログラマーが少なくとも1回は読むべき本です。

于 2010-02-14T08:19:49.273 に答える