二分探索法(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)