探索/二分探索法 - nkym_memo @ ウィキ

二分探索法(binary search)

• 順に整列された配列に対して探索を行う
• 探索範囲の中央で２分し、中央値に対して大小で探索範囲を縮める

struct{
  int key;
  int data;
}table[100];

int ndata;

int binary_search(int key)
{
  int low = 0;
  int high = n-1;
  int middle;

  while(low <= high){
    middle = (low + high)/2;
    if(key == table[middle].key){
      return (table[middle].data);
    }else if(key < table[middle].key){
	high = middle -1;
    }else{
      low = middle +1;
    }
  }
  return -1;
}

サンプルプログラム

• 二分探索法サンプル

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)