이진 탐색(Binary Search)은 정렬된 배열에서 특정 요소(목표값)의 위치를 빠르게 찾아내는 대표적인 탐색 알고리즘입니다. 이진 탐색을 적용하기 전에는 배열이 반드시 사전에 정렬되어 있어야 한다는 점을 기억하세요.
이진 탐색은 로그 검색(logarithmic search), 바이너리 초프(binary chop), 절반 구간 탐색(half interval search)이라는 이름으로도 알려져 있습니다.
이진 탐색의 작동 원리
이진 탐색 알고리즘은 찾으려는 요소를 배열의 중간(middle) 요소와 먼저 비교하고, 그 비교 결과에 따라 아래와 같은 절차를 따릅니다.
경우 1 − element = middle : 요소를 찾았으므로 해당 인덱스를 반환합니다.
경우 2 − element > middle : middle+1 인덱스부터 n까지의 하위 배열에서 요소를 다시 탐색합니다.
경우 3 − element < middle : 0 인덱스부터 middle−1까지의 하위 배열에서 요소를 다시 탐색합니다.
알고리즘 단계
매개변수: initial_value, end_value
Step 1 : middle = initial_value + (end_value - initial_value) / 2 ; 공식을 이용해 배열의 중간 요소를 찾습니다. Step 2 : 만약 middle == element라면 'element found' 메시지와 함께 해당 인덱스를 반환합니다. Step 3 : 만약 middle > element라면 end_value = middle - 1로 설정하고 함수를 다시 호출합니다. Step 4 : 만약 middle < element라면 start_value = middle + 1로 설정하고 함수를 다시 호출합니다. Step 5 : 종료(exit)합니다.
참고로, 중간값 계산 시 (start_index + end_index) / 2 대신 start_index + (end_index - start_index) / 2 형태를 사용하면 두 인덱스의 합이 커질 때 발생할 수 있는 정수 오버플로우를 예방할 수 있습니다.
이진 탐색 알고리즘 함수는 동일한 작업을 반복 수행하는 방식으로 구현되며, 이 호출은 크게 두 가지 유형으로 나눌 수 있습니다.
- 반복(Iterative) 방식
- 재귀(Recursive) 방식
반복 호출(Iterative call)은 while이나 for 문처럼 동일한 코드 블록을 여러 번 반복 실행하는 방식입니다.
재귀 호출(Recursive call)은 동일한 함수가 자기 자신을 계속해서 다시 호출하는 방식입니다.
반복 호출을 이용한 이진 탐색 구현 프로그램
예제 코드
#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
while (start_index <= end_index){
int middle = start_index + (end_index- start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] < element)
start_index = middle + 1;
else
end_index = middle - 1;
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 16;
int found_index = iterativeBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
}
실행 결과
Element found at index : 4
배열 {1, 4, 7, 9, 16, 56, 70}에서 값 16을 찾으면, 16은 배열의 다섯 번째 위치(인덱스 4)에 있으므로 위와 같이 출력됩니다.
재귀 호출을 이용한 이진 탐색 구현 프로그램
예제 코드
#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
if (end_index >= start_index){
int middle = start_index + (end_index - start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] > element)
return recursiveBinarySearch(array, start_index, middle-1, element);
return recursiveBinarySearch(array, middle+1, end_index, element);
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 9;
int found_index = recursiveBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
}
실행 결과
Element found at index : 3
같은 배열에서 값 9를 찾으면, 9는 인덱스 3에 위치하므로 위와 같이 출력됩니다.
시간 복잡도
이진 탐색은 한 번의 비교마다 탐색 범위가 절반씩 줄어들기 때문에 시간 복잡도가 O(log n)으로 매우 효율적입니다. 최선의 경우(중간 요소가 곧 목표값일 때)에는 O(1)이며, 처음부터 끝까지 차례대로 확인하는 선형 탐색의 O(n)보다 훨씬 빠릅니다. 따라서 대량의 정렬된 데이터를 다룰 때 특히 유용하게 활용할 수 있습니다.