크기가 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]3568101315161721232627293133
C언어로 표현된 함수 func를 이용하여 정수 K가 저장된 위치를 검색하려고 한다. func(E, 0, 15, 27)를 호출했을 때, 검색이 완료되기까지 ㉠ 문장이 수행되는 횟수는?
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이 아니다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 13년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기