[アルゴリズム]バイナリ検索

バイナリ検索を理解する前に、通常の順序で検索されるコードを見てみましょう.
[Sequential Search Pseudo code]

void seqsearch(int n, const keytype S[], keytype x, index & location)
{

    location =1;
    while(location <=n && S[location] !=x)
    {
      location++;
      if(location > n) location=0;
    }

}

ここで、nは要素数、Sはkeytype形状の配列であり、その大きさはnである.xは検索する要素の値を表し、locationはその位置を表す.
この場合、最悪の場合、最も重要な位置がアレイの最後尾にある場合、nとなる.
最良の場合、最初の位置は1です.Best(n) =1 , Worst(n)=nバイナリ検索を正式に理解しましょう.

バイナリサーチ

バイナリ検索は、シーケンス検索と同様に、リスト内で特定の値を検索するアルゴリズムです.しかし、違いもあります.これはソートされたリスト内で検索します.
順番検索とは異なり、リストに載っているベビーシッターから始めます.
基本アルゴリズムの方式はこうです.
1)アレイの中程度の大きさ(=n/2)を求め、中程度の大きさの上記差Mをxと比較する.
2-1)xがMより大きい場合、次の検索の開始点は、中間点でセルの右側の位置になります.
2−2)xがMより小さい場合、次の探索の終了点は、中間点で左の一コマとなる.
2-3)xとmの値が同じ場合、検索を終了します.
[Binary Search Pseudo code]

void binarySearch(int n, const keytype S[], keytype x, index & location)
{
	index low, high, mid;
    low =1;
    high =n;
    location =0;
    
    while(low<= high && location == 0 ) 
    {
      mid = (low + high ) / 2;
      if(S[mid] == x ) location == mid; // location에 위치를 저장하고 while 문을 벗어난다.
      else if( S[mid] > x ) low = mid +1;
      else high = mid - 1;
    }

}

コードから見ると、もっと簡潔な感じがします.

[解析]

Q)二分探索アルゴリズムを用いて鍵を探すためには,S上の幾つかの項目を探索する必要がある.
A)While文を実行するたびに検索対象の合計サイズが半分になるので、最悪の場合はlg n+1個だけ検索すればよい.(lg= log2)