알파벳 순으로 정렬된 다음 배열에 대하여 이진 탐색으로 원소 P를 찾으… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 24년 1회차
알파벳 순으로 정렬된 다음 배열에 대하여 이진 탐색으로 원소 P를 찾으려고 할 때, 비교해야 할 원소의 개수는?
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C | E | G | H | J | L | M | N | P | Q | S | T | V | W | Z |
1
2
2
3
3
4
4
5
해설
원소 P를 찾기까지 4개의 원소와 비교한다.
이진 탐색은 범위의 중간 인덱스 의 원소와 비교하며 범위를 절반씩 줄인다. 비교 순서는 N → T → Q → P이다.
범위 0~14, 중간 7(N) < P → 범위 8~14
중간 11(T) > P → 범위 8~10
중간 9(Q) > P → 범위 8~8
중간 8(P) 일치 → 탐색 종료
- 2개는 N, T까지만 비교한 상태로 아직 P에 도달하지 않았다.
- 3개는 Q까지만 비교한 상태로 범위 8~8의 P가 남아 있다.
- 5개는 P를 찾은 뒤에도 비교를 계속한 값으로, 일치하는 순간 탐색은 끝난다.
오류나 개정된 내용이 보이면 알려주세요