다음은 이진 탐색을 수행하는 C 함수이다. 이 함수를 사용하여 0부터 … | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 19년 1회차
다음은 이진 탐색을 수행하는 C 함수이다. 이 함수를 사용하여 0부터 20까지의 정수가 차례대로 저장되어 있는 배열 b에 대한 이진 탐색을 수행할 때, key 값과 a[middle] 값을 비교하는 횟수가 다른 것은? (단, 배열의 색인은 0부터 시작한다)int binarySearch(int *a, int key, int low,
int high)
{
int middle;
while (low <= high) {
middle = (low + high) / 2;
if (key == a[middle])
return middle;
else if (key > a[middle])
low = middle + 1;
else
high = middle - 1;
}
return -1;
}
1
binarySearch(b, 4, 1, 20)
2
binarySearch(b, 7, 1, 20)
3
binarySearch(b, 9, 1, 20)
4
binarySearch(b, 14, 1, 20)
해설
비교 횟수가 다른 것은 key가 7인 호출로, 3회 만에 찾는다. 나머지는 모두 5회이다.
low = 1, high = 20에서 시작하고 b[i] = i이므로 middle 값이 곧 비교 대상 값이다. key 7은 middle이 10, 5, 7로 바뀌며 세 번째 비교에서 찾는다. 반복마다 수행하는 비교를 모두 세어도 이 호출만 짧다.
- key 4는 middle이 10, 5, 2, 3, 4로 바뀌어 5회 비교한다.
- key 9는 middle이 10, 5, 7, 8, 9로 바뀌어 5회 비교한다.
- key 14는 middle이 10, 15, 12, 13, 14로 바뀌어 5회 비교한다.
오류나 개정된 내용이 보이면 알려주세요