7

二分探索アルゴリズムでは、次の 2 つの比較があります。

if (key == a[mid]) then found;

else if (key < a[mid]) then binary_search(a[],left,mid-1);
      else binary_search(a[],mid+1,right);

上記の2つではなく、1つだけ比較できる方法はありますか。

--

ありがとう

Alok.Kr.

4

7 に答える 7

15

見る：

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

ウィキから取得：

   low = 0
   high = N
   while (low < high) {
       mid = low + ((high - low) / 2)
       if (A[mid] < value)
           low = mid + 1;
       else
            //can't be high = mid-1: here A[mid] >= value,
            //so high can't be < mid if A[mid] == value
            high = mid;
   }
   // high == low, using high or low depends on taste
   if ((low < N) && (A[low] == value))
       return low // found
   else
       return -1 // not found

ウィキからの長所/短所: 「このアプローチは、一致の発見時に早期終了の可能性を放棄するため、成功した検索には、予想される log2(N) − 1 反復ではなく、log2(N) 反復があります。一方、この実装では、より少ない比較: log2(N) は、N が 8 より大きい場合、1·5 (log2(N) − 1) の 2 つのテストの実装で予想される比較の数よりも少なくなります。

于 2010-08-17T07:30:13.177 に答える
4

はい。mid再帰呼び出しから除外しないでください。

if ( left == right ) return NULL;
if ( left + 1 == right ) return key == a[left]? &a[left] : NULL;

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

if (key < a[mid]) return binary_search(a[],left,mid-1);
else return binary_search(a[],mid,right); // include `mid` in next round

O（logN）パフォーマンスを実現するには、再帰ごとにセットの半分を削除するだけで済みます。あなたはhalf+1を排除することによって、さらに上を行きます。

再帰中にのみ使用する場合<、アルゴリズムは、より小さくないkey（ただし、より大きくなる可能性があるkey）最小の要素を検出します。単一の同等性テストを実行して終了します。

于 2010-08-17T07:23:27.777 に答える
2

アセンブラでは、次のことができます。

cmp key,a[mid]
beq found
bge else

したがって、コンパイラがのぞき穴の最適化に非常に優れている場合は、すでにこれを行っている可能性があります。

于 2010-08-17T07:24:29.900 に答える
0 
for (step = 0; step < n; step <<= 1);

for (i = 0; step; step >>= 1)
    if (i + step < n && v[i + step] <= x)
        i += step;
于 2010-08-17T13:03:16.930 に答える
0

これは再帰的なアルゴリズムです。最初の比較は停止基準と2番目の実際の検索であるため、それらを削除することはできません。

最初に、要素を既に見つけたときはいつでも、次に配列のどの部分で要素を探すかを尋ねます。したがって、1つの比較だけに基づいてこれらの決定を行うことはできません。

于 2010-08-17T07:22:37.963 に答える
0

わかりました、これは Adob​​e でのインタビューの質問でした。私はこれを行う方法を理解しようとしていました。

今、私はそれに対する解決策を持っているので、投稿しています

void binary_search (int a[] , int low ,  int high , int key )
{
    int mid = (low+high)/2;

    if (key == a[mid]) {
        printf ("Number Found\n");
        return;
    }

    else {
        int sign = Calc_sign (key-a[mid]);
        low = low*sign + (1-sign)*mid;
        high = mid*sign + (1-sign)*right;
        binary_search (a,low,high,key);
    }
}

int Calc_sign(int a) 
{
     return ( (a & 80000000) >> 31);
}

そのため、コードでは、keyvalue が mid 要素と等しいかどうかを確認するための比較は 1 つだけです。

--

ありがとう

Alok Kr.

于 2010-08-17T14:12:56.353 に答える
0

まず最初に、プログラムを最適化する必要がありますか? どこでそれを行う必要があるかを知るために測定しましたか? この関数にありますか？

プリミティブ型の場合、2 番目の比較は非常に高速な操作です。比較のコストが高くなるのは、要素を適切なレジスタにロードすることであり、これは最初の比較に必要です。その比較が実行されると、値はすでにレジスターにあり、2 番目の操作では、単一のプロセッサー命令に加えて、分岐予測ミスのコストがかかります。

整数型を想定すると、コンパイラが末尾再帰の最適化を実行できない場合、アルゴリズムのプロセッサ時間のコストは、おそらく再帰呼び出しのコストによって支配されます。これを本当に最適化する必要がある場合は、すべての最適化フラグをオンにしてコンパイルし、アセンブラを分析して、末尾再帰の最適化が適用されているかどうかを確認してください。そうでない場合は、アルゴリズムを再帰から反復に手動で変換します。

これには 2 つの効果があります。コードを不明瞭にする (本当に必要でない限り、クリーンなソリューションを変更しないようにする) ことと、関数呼び出しを避けることです。

C++ について話していて、型が複雑で、オーバーロードされた比較演算子が高価である場合、パフォーマンスの最速の向上は、より小さい場合、等しい場合compareは負の数を返し、より大きい場合は正の数を返すメソッドを実装することです。よりも。次に、比較の前に結果を事前計算してから、整数のみのチェックを実行します。これにより、アルゴリズムの全体的なコストが、コストのかかる比較による実際のオブジェクトの単一処理に取り除かれ、元の仮定に戻ります。0

于 2010-08-17T07:53:38.260 に答える