バイナリサーチ (Binary Search)

C 言語による実装

bsearch.c

/*
  バイナリサーチ (Binary Search):
  ソート済みの配列において, 検索する間隔を半分に分轄しながらデータ
  を探し出すアルゴリズム.
  ソート済みの配列を分轄するということはバイナリサーチツリーを生成
  することになる.
  検索範囲の分轄はデータの大小関係をもとに行われる.
*/

/*
  アルゴリズム分析:
  1. 配列をソートする (ここでは昇順でソートされたとする)
  2. 配列の中央にある要素を調べる
  3. 探索
    ・中央の要素が目的の値ではなく, 目的の値が中央の値より大きい場合,
      中央より後半の部分を調べる
    ・中央の要素が目的の値ではなく, 目的の値が中央の値より小さい場合,
      中央より前半の部分を調べる
  4. STEP 2 に戻る
*/

/*
  バイナリサーチは値の比較によって検索範囲を絞り込むので,
  探索対象の配列がソートされていなげればならない.
  時間計算量は O( log_2(n) )
*/

#include <stdio.h>

int main(void){
  int array[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; /* sorted array */
  int left = 0; /* start key of index */
  int right = 9; /* end key of index */
  int mid; /* midle key of index */
  int value; /* search value */

  printf("Find value?\n");
  scanf("%d", &value);
  
  while(left <= right){
    /* calc of middle key */
    /* left が 0 であっても大丈夫 */
    mid = (left + right) / 2;

    if(array[mid] == value){
      printf("Found!\n");
      return 0;
    }
    else if(array[mid] < value){
      left = mid + 1; 
    }
    else{
      right = mid - 1;
    }
  }
  printf("Not found\n");
  
  return 0;
}

bsearch.c の実行結果は:

[cactus:~/code_c/ad]% ./bsearch
Find value?
10
Found!
[cactus:~/code_c/ad]% ./bsearch
Find value?
20
Found!
[cactus:~/code_c/ad]% ./bsearch
Find value?
90
Found!
[cactus:~/code_c/ad]% ./bsearch
Find value?
100
Found!
[cactus:~/code_c/ad]% ./bsearch
Find value?
30
Found!
[cactus:~/code_c/ad]% ./bsearch
Find value?
39
Not found