binarySearch  2분 탐색

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;
}

1회의 비교로 탐색해야 할 범위는 반이 되므로, 탐색 성공 혹은 실패의 어느 쪽의 경우에서도, 계산량은 O(log n)이다.

데이터가 내림차순으로 소트 되고 있는 경우는, 부등호의 방향을 변하면 좋다.