Cで二分サーチ
何も考えずにひたすら配列の要素とキーを比較する線形サーチに対して、要素数の多い配列のキーを比較するには二分サーチがよい。
これは、１度検索を行う度に検索対象を半分に縮めていく。
たとえば、配列数が10億としても30回前後検索をすればターゲット情報がわかる、ということだ。
単純に比較を繰り返す線形サーチだと最悪の場合配列の要素数分比較を行うことになる。
二分サーチがどれだけ線形サーチに比べて効率的か一目瞭然だ。
が、二分サーチはソートされている配列にしか使えないという欠点もある。
ソートされていない場合は線形サーチを使うか、ソート後に二分サーチを用いる必要がある。
int binarySearch(int array[], int key, int low, int high) {
int middle;
while( low <= high )
{
middle = ( low + high ) / 2;
if( key == array[middle] ) return middle;
else if( key < array[middle] ) high = middle - 1;
else low = middle + 1;
}
return -1;
}まずは中間要素を求める。
中間要素が探索キーと等しければその配列要素を返す。
中間要素が探索キーより大きければ、探索範囲の開始位置を修正。
中間要素が探索キーより小さければ、探索範囲の終了位置を修正。
一致する要素が見つかるか、要素自体がなくなるまでこれを繰り返す。
