2022년도 2회 정보처리기사 기출문제 22번

22. 다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾을 경우 비교되는 횟수는?

 

  ① 2                  ❷ 3

  ③ 4                  ④ 5   

 

이 문제는 이진 검색(Binary Search) 방법을 이용해 주어진 값인 14를 찾는 과정에서 비교되는 횟수를 묻고 있습니다.

1. 이진 검색 방법에 대한 간단한 설명

이진 검색은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 기본적으로 배열의 중간값을 기준으로 값을 비교하고, 찾고자 하는 값이 중간값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 다시 검색하는 방식입니다. 이 과정을 반복하면서 찾고자 하는 값을 좁혀 나갑니다.

2. 주어진 배열과 찾을 값

• 배열: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
• 찾을 값: 14

3. 이진 검색을 적용한 과정

1. 처음 배열의 크기는 15입니다. 중간 인덱스를 계산합니다.
   • 중간값의 인덱스: 0+142=7\frac{0 + 14}{2} = 720+14​=7 (소수점 버림)
   • 배열의 인덱스 7에 있는 값은 8입니다.
   • 14는 8보다 크므로 오른쪽 절반을 살펴봅니다.
2. 오른쪽 절반 배열: 9, 10, 11, 12, 13, 14, 15
   • 중간값의 인덱스: 7+142=10\frac{7 + 14}{2} = 1027+14​=10
   • 배열의 인덱스 10에 있는 값은 11입니다.
   • 14는 11보다 크므로 오른쪽 절반을 살펴봅니다.
3. 오른쪽 절반 배열: 12, 13, 14, 15
   • 중간값의 인덱스: 11+142=12\frac{11 + 14}{2} = 12211+14​=12
   • 배열의 인덱스 12에 있는 값은 13입니다.
   • 14는 13보다 크므로 오른쪽 절반을 살펴봅니다.
4. 오른쪽 절반 배열: 14, 15
   • 중간값의 인덱스: 13+142=13\frac{13 + 14}{2} = 13213+14​=13
   • 배열의 인덱스 13에 있는 값은 14입니다.
   • 14를 찾았으므로 검색을 종료합니다.

4. 비교 횟수 분석

• 첫 번째 비교: 8과 14를 비교 → 1번 비교
• 두 번째 비교: 11과 14를 비교 → 2번 비교
• 세 번째 비교: 13과 14를 비교 → 3번 비교
• 네 번째 비교: 14와 14를 비교 → 4번 비교

따라서, 14를 찾기까지 총 4번의 비교가 이루어졌습니다.

5. 결론

이진 검색을 사용하면 값이 정렬된 배열에서 반복적으로 배열을 반으로 나누면서 탐색을 진행하기 때문에 빠르게 원하는 값을 찾을 수 있습니다. 이 문제에서는 14를 찾을 때 4번의 비교가 이루어졌습니다.

6. 기타 고려사항

• 이진 검색의 시간 복잡도는 **O(log n)**입니다. 즉, 배열의 크기가 커질수록 비교 횟수는 상대적으로 적어지므로 효율적입니다.