다음은 정렬된 정수 배열에 대한 이진 탐색(binary search)을… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 25년 1회차
다음은 정렬된 정수 배열에 대한 이진 탐색(binary search)을 구현한 C 코드이다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?int BSearch(int data[], int size, int target) {
int mid, left = 0, right = size - 1;
while(left <= right) {
mid = [ (가) ];
if(target == data[mid]) return mid;
else if(target > data[mid]) left = [ (나) ];
else right = [ (다) ];
}
return -1;
}(가) (나) (다)1
(left+right) // 2 mid-1 mid+1
2
right-(left-right) // 2 mid left
3
(left+right) / 2 mid+1 mid-1
4
left+(right-left) / 2 right mid
해설
중간 인덱스는 (left+right) / 2이고, 찾는 값이 크면 left = mid+1, 작으면 right = mid-1로 범위를 줄인다.
C에서 정수끼리의 /는 몫만 남기는 정수 나눗셈이다. 이미 비교한 mid는 다음 범위에서 제외해야 범위가 매번 줄어 반복이 끝난다.
- (left+right) // 2, mid-1, mid+1: C에서 //는 주석 기호이고, 찾는 값이 클 때 left를 mid-1로 두면 탐색 방향이 반대가 된다.
- right-(left-right) // 2, mid, left: 중간값 식이 틀렸고, left = mid로 두면 범위가 줄지 않아 무한 반복될 수 있다.
- left+(right-left) / 2, right, mid: 중간값 식은 맞지만 left = right, right = mid로는 범위를 올바르게 좁히지 못한다.
오류나 개정된 내용이 보이면 알려주세요