리스트가 정렬되어 있는 경우, 이진 검색(Binary Search) 기법을 활용하면 원하는 항목을 매우 효율적으로 찾을 수 있습니다. 이진 검색은 리스트 전체를 두 개의 하위 리스트로 계속 나누어 가며 탐색하는 방식입니다. 먼저 리스트의 중간 위치에 있는 값을 확인하고, 그 값이 찾으려는 항목과 일치하면 해당 위치를 즉시 반환합니다. 일치하지 않으면 탐색 대상을 왼쪽 또는 오른쪽 하위 리스트로 좁혀 같은 과정을 반복하며, 항목을 찾거나 탐색 범위가 소진될 때까지 진행합니다.
이진 검색의 복잡도
- 시간 복잡도: 최선의 경우 O(1), 평균 및 최악의 경우 O(log₂ n)
- 공간 복잡도: O(1)
입력과 출력
입력:
정렬된 데이터 목록: 12 25 48 52 67 79 88 93
탐색 키: 79
출력:
항목 발견 위치: 5
알고리즘
binarySearch(array, start, end, key)
입력 − 정렬된 배열, 시작 위치(start), 끝 위치(end), 탐색 키(key)
출력 − 키가 존재하면 해당 위치, 존재하지 않으면 유효하지 않은 값(-1)
Begin
if start <= end then
mid := start + (end - start) / 2
if array[mid] = key then
return mid // 키 발견, 위치 반환
if array[mid] > key then
call binarySearch(array, start, mid-1, key) // 왼쪽 절반 탐색
else // array[mid] < key
call binarySearch(array, mid+1, end, key) // 오른쪽 절반 탐색
else
return invalid location // 유효하지 않은 위치 반환
End
C++ 구현 예제
#include<iostream>
using namespace std;
int binarySearch(int array[], int start, int end, int key) {
if(start <= end) {
int mid = (start + (end - start) / 2); // 리스트의 중간 위치
if(array[mid] == key)
return mid;
if(array[mid] > key)
return binarySearch(array, start, mid-1, key); // 왼쪽 절반 탐색
return binarySearch(array, mid+1, end, key); // 오른쪽 절반 탐색
}
return -1; // 찾지 못한 경우
}
int main() {
int n, searchKey, loc;
cout << "항목의 개수를 입력하세요: ";
cin >> n;
int arr[n]; // 크기 n인 배열 생성
cout << "항목을 입력하세요: " << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "리스트에서 찾을 탐색 키를 입력하세요: ";
cin >> searchKey;
if((loc = binarySearch(arr, 0, n-1, searchKey)) >= 0)
cout << "항목 발견 위치: " << loc << endl;
else
cout << "리스트에서 항목을 찾지 못했습니다." << endl;
}
동작 과정 살펴보기
위 예제에서 탐색 키 79를 찾는 과정은 다음과 같습니다.
- 전체 범위(인덱스 0~7)의 중간 인덱스 3에 있는 값 52를 확인합니다. 52 < 79이므로 오른쪽 절반을 탐색합니다.
- 새로운 범위(인덱스 4~7)의 중간 인덱스 5에 있는 값 79를 확인합니다. 탐색 키와 일치하므로 인덱스 5를 반환합니다.
이처럼 이진 검색은 한 번의 비교마다 탐색 범위가 절반으로 줄어들기 때문에, 요소가 n개일 때 최대 약 log₂n번의 비교만으로 원하는 값을 찾을 수 있습니다. 단, 반드시 배열이 오름차순으로 정렬되어 있어야 한다는 전제 조건이 필요합니다.
실행 결과
항목의 개수를 입력하세요: 8 항목을 입력하세요: 12 25 48 52 67 79 88 93 리스트에서 찾을 탐색 키를 입력하세요: 79 항목 발견 위치: 5