유일 키를 갖는 자료 1,000개가 키에 의해 오름차순으로 정렬되어 있… | [무선설비기사 필기] 19년 1회차 기출문제 상세 페이지

1[무선설비기사 필기] 19년 1회차

유일 키를 갖는 자료 1,000개가 키에 의해 오름차순으로 정렬되어 있다. 이진탐색(Binary Search) 방법으로 원하는 자료를 찾고자 할 경우 최대 몇 번의 키 비교를 해야 하는가?

5번

10번

500번

1,000번

해설

자료 1,000개를 이진탐색으로 찾을 때 최대 비교 횟수는 10번이다.
이진탐색은 비교할 때마다 탐색 범위가 절반으로 줄어들므로 필요한 비교 횟수는  $\lceil \log_2 N \rceil$ 로 구한다.
 $2^9 = 512 \lt 1{,}000 \le 1{,}024 = 2^{10}$ 이므로 최대 10회의 키 비교로 원하는 자료를 찾을 수 있다.

내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→