binarySearch  ２分探索

int binarySearch(DATA *data, int nmem, int target);

typedef struct {
    int key;        /* 比較のキーとなるフィールド */
    int info;       /* その他のフィールド */
} DATA;

data    （入力）データレコードの配列
nmem    （入力）レコード配列の大きさ
target  （入力）探索目標とするキーの値

見つかった場合は配列の要素番号（配列の先頭要素の番号は0）。
見つからなかった場合は -1。

int binarySearch(DATA *data, int nmem, int target){
    int left, right, middle;

    left = 0;
    right = nmem - 1;
    while (left < right) {
        middle = (left + right) / 2;
        if ((data + middle)->key < target) left = middle + 1;
        else right = middle;
    }
    if ((data + left)->key == target) 
        return left;
    return -1;
}

１回の比較で探索すべき範囲は半分になるので、探索成功あるいは失敗の どちらの場合でも、計算量は O(log n) である。

データが降順でソートされている場合は、不等号の向きを変ればよい。