다음 C 코드는 이진 탐색을 이용하여 정수 데이터를 탐색하는 함수이다.… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지

다음 C 코드는 이진 탐색을 이용하여 정수 데이터를 탐색하는 함수이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, key는 찾고자 하는 값, a[]는 오름차순으로 정렬된 정수 배열, n은 배열의 크기이다)
int search(int key, int a[], int n) {
    int mid;
    int left = 0;
    int right = n-1;
    while ([ (가) ]) {
        mid = (right + left) / 2;
        if (key == a[mid]) return mid;
        if ([ (나) ]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}
(가)　　(나)

left < right　　key < a[mid]

left < right　　key > a[mid]

left <= right　　key < a[mid]

left <= right　　key > a[mid]

(가) left <= right, (나) key < a[mid]이다.
원소 하나만 남은 left == right 구간도 검사해야 하므로 등호가 필요하다. key가 a[mid]보다 작으면 왼쪽 절반에 있으므로 right = mid - 1로 구간을 줄인다.
left < right, key < a[mid]: 원소 하나가 남은 구간을 검사하지 않아 찾지 못하는 경우가 생긴다.
left < right, key > a[mid]: 등호 누락에 더해 구간을 반대 방향으로 줄인다.
left <= right, key > a[mid]: key가 클 때 오른쪽 끝을 줄여 탐색 방향이 뒤집힌다.