크기가 16인 다음 배열 E에 정수가 저장되어 있다.i[0][1][2]… | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 13년 1회차
크기가 16인 다음 배열 E에 정수가 저장되어 있다.
| i | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] | [13] | [14] | [15] |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| E[i] | 3 | 5 | 6 | 8 | 10 | 13 | 15 | 16 | 17 | 21 | 23 | 26 | 27 | 29 | 31 | 33 |
int func(int E[ ], int first, int last, int K)
{
int mid;
if (last < first) return -1;
else {
㉠ mid = (first + last) / 2;
if (K == E[mid]) return mid;
else if (K < E[mid]) return func(E, first, mid-1, K);
else return func(E, mid+1, last, K);
}
}
1
1회
2
2회
3
3회
4
4회
해설
func는 재귀 이진 탐색이며, 27을 찾을 때까지 ㉠은 4회 수행된다.
(0, 15): mid = 7, E[7] = 16 < 27 → 오른쪽
(8, 15): mid = 11, E[11] = 26 < 27 → 오른쪽
(12, 15): mid = 13, E[13] = 29 > 27 → 왼쪽
(12, 12): mid = 12, E[12] = 27 → 찾음
- 1회: 첫 mid의 값이 16이라 바로 찾지 못한다.
- 2회: 두 번째 mid의 값은 26이다.
- 3회: 세 번째 mid의 값은 29로 아직 27이 아니다.
오류나 개정된 내용이 보이면 알려주세요