이진 탐색이란?
이진 탐색(Binary Search)은 정렬된 리스트에만 적용할 수 있는 효율적인 탐색 방법입니다. 탐색 범위를 절반씩 줄여가며 원하는 값을 찾기 때문에 선형 탐색보다 훨씬 빠른 성능을 보입니다.
동작 방식은 다음과 같습니다. 주어진 리스트를 두 개의 동일한 부분으로 나눈 뒤, 찾고자 하는 키(key) 값을 리스트의 중간 요소와 비교합니다.
이진 탐색에서 발생하는 세 가지 경우
- 중간 요소가 키 값과 일치하면 → 탐색이 성공적으로 종료됩니다.
- 중간 요소가 키 값보다 크면 → 왼쪽 부분에서 탐색을 계속 진행합니다.
- 중간 요소가 키 값보다 작으면 → 오른쪽 부분에서 탐색을 계속 진행합니다.
입력과 출력
입력(Input)
- 정렬된 요소들의 리스트
- 찾고자 하는 키 값
출력(Output)
- 성공(Success): 키 값을 찾은 경우
- 실패(Unsuccessful): 키 값을 찾지 못한 경우
C 언어 이진 탐색 예제 코드
다음은 이진 탐색을 구현한 C 프로그램입니다.
#include<stdio.h>
int main(){
int a[50], n, i, key, flag = 0, low, mid, high;
printf("enter the no: of elements:");
scanf ("%d",&n);
printf("enter the elements:");
for(i=0; i<n; i++)
scanf( "%d", &a[i]);
printf("enter a key element:");
scanf ("%d", &key);
low = 0;
high = n-1;
while (low<= high ){
mid = (low + high) /2;
if (a[mid] == key){
flag = 1;
break;
} else {
if (a[mid] > key)
high = mid-1;
else
low = mid+1;
}
}
if (flag == 1)
printf ("search is successful");
else
printf("search is unsuccessful");
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
enter the no: of elements:5 enter the elements:23 45 57 89 90 enter a key element:45 search is successful
코드 핵심 포인트 정리
- low, high 변수: 현재 탐색 범위의 시작 인덱스와 끝 인덱스를 나타냅니다.
- mid = (low + high) / 2: 매 반복마다 탐색 범위의 중간 위치를 계산합니다.
- flag 변수: 키 값을 찾았는지 여부를 저장하며, 루프 종료 후 성공 여부를 판단하는 데 사용됩니다.
- 탐색 범위 축소: 키 값이 중간 요소보다 작으면 high를 mid-1로, 크면 low를 mid+1로 갱신하여 탐색 범위를 절반으로 줄입니다.
이진 탐색은 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도가 O(log n)으로, 요소 개수가 많아질수록 선형 탐색(O(n))에 비해 압도적으로 빠릅니다. 단, 반드시 데이터가 사전에 정렬되어 있어야 한다는 점을 기억해야 합니다.