이진 탐색(binary search)은 로그 탐색(logarithmic search)이라고도 불리며, 정렬된 배열에서 특정 원소를 빠르게 찾는 대표적인 탐색 알고리즘입니다. 이 알고리즘은 배열을 계속 절반씩 나누어(divide) 탐색 범위를 좁혀 가는 방식으로 동작합니다. 중간 위치에서 원소를 찾으면 바로 결과를 반환하고, 찾지 못하면 남은 범위를 다시 나누어 확인하는 과정을 원소를 발견할 때까지 반복합니다.
동작 원리
이진 탐색은 정렬된 배열의 중간 원소와 찾고자 하는 값을 비교하는 방식으로 진행됩니다.
- 찾으려는 값이 중간 원소와 같으면 탐색에 성공한 것이므로 해당 원소의 위치(인덱스)를 기준으로 결과를 반환합니다.
- 찾으려는 값이 중간 원소보다 크면 오른쪽 부분 배열, 즉 중간 원소의 다음 위치부터 배열 끝까지의 범위에서 다시 탐색합니다.
- 찾으려는 값이 중간 원소보다 작으면 왼쪽 부분 배열, 즉 배열의 첫 번째 원소부터 중간 원소 앞 위치까지의 범위에서 다시 탐색합니다.
이처럼 한 번의 비교마다 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log n)으로 매우 효율적이며, 데이터 양이 클수록 그 장점이 두드러집니다.
문법
C++ STL에서 제공하는 표준 이진 탐색 함수는 다음과 같은 형식으로 호출합니다.
binary_search(start_address, end_address, element)
매개변수
- start_address : 탐색을 시작할 배열의 첫 번째 원소의 주소
- end_address : 탐색 범위의 끝을 나타내는 주소(마지막 원소의 다음 위치)
- element : 배열 안에서 찾고자 하는 원소
반환값
찾으려는 원소가 배열에 존재하면 true, 존재하지 않으면 false를 반환합니다. 즉, 이 함수는 원소의 실제 인덱스가 아니라 존재 여부만 알려줍니다. 만약 원소의 정확한 위치가 필요하다면 lower_bound()나 upper_bound() 함수를 함께 활용하는 것이 좋습니다.
예제 코드
#include <algorithm>
#include <iostream>
using namespace std;
void printArray(int a[], int arraysize) {
for (int i = 0; i < arraysize; ++i)
cout << a[i] << " ";
}
int main() {
int arr[] = {1, 5, 9, 7, 3, 2, 0, 4};
int sizeofarr = sizeof(arr) / sizeof(arr[0]);
cout << "배열의 원소는 다음과 같습니다:\n";
printArray(arr, sizeofarr);
cout << "\n배열의 원소를 정렬합니다.";
sort(arr, arr + sizeofarr);
cout << "\n정렬된 배열 : ";
printArray(arr, sizeofarr);
cout << "\n찾으려는 원소는 4입니다.";
if (binary_search(arr, arr + sizeofarr, 4))
cout << "\n원소를 찾았습니다.";
else
cout << "\n원소를 찾지 못했습니다.";
}실행 결과
배열의 원소는 다음과 같습니다: 1 5 9 7 3 2 0 4 배열의 원소를 정렬합니다. 정렬된 배열 : 0 1 2 3 4 5 7 9 찾으려는 원소는 4입니다. 원소를 찾았습니다.
주의 사항
binary_search()를 호출하기 전에는 반드시 sort() 등을 이용해 배열을 오름차순으로 정렬해야 합니다. 정렬되지 않은 배열에 이진 탐색을 적용하면 올바른 결과를 보장할 수 없습니다.