C 언어로 구현하는 이진 탐색: 반복문과 재귀 호출 방법 총정리

이진 탐색(Binary Search) 알고리즘은 비교와 분할 메커니즘에 기반해 동작하는 대표적인 탐색 알고리즘입니다. 하프 인터벌 탐색(half-interval search), 로그 탐색(logarithmic search), 또는 바이너리 초프(binary chop)라고도 불립니다.

이진 탐색은 정렬된 배열 안에서 목표 값(target value)의 위치를 찾습니다. 먼저 목표 값을 배열의 중간 요소와 비교하는데, 두 값이 같다면 알고리즘은 해당 요소의 인덱스를 반환합니다. 만약 값이 같지 않다면 배열을 절반으로 나눠 탐색 범위를 좁히는데, 목표 값이 중간 값보다 작으면 배열의 앞쪽 절반을, 크면 뒤쪽 절반을 사용한 뒤 동일한 과정을 반복합니다.

입력:
A[] = {0,2,6,11,12,18,34,45,55,99}
n = 55

출력:
55 at Index = 8

동작 원리

위 예제 배열에서 55를 찾는 과정은 다음과 같습니다.

먼저 55를 배열의 중간 요소인 18과 비교합니다. 18이 55보다 작으므로 배열의 뒤쪽 절반인 {24, 45, 55, 99}를 새로운 탐색 범위로 삼습니다.
새 범위의 중간 요소는 55입니다. 검색 값과 일치하므로 이 값의 인덱스인 8을 반환합니다.

만약 검색 값이 중간 요소보다 작았다면 앞쪽 절반을 사용했을 것이며, 값을 찾거나 더 이상 나눌 수 없을 때까지 이 과정을 계속 반복하게 됩니다.

C 언어로 이진 탐색을 구현하는 방법은 크게 두 가지가 있으며, 두 방법의 차이는 탐색 함수를 호출하는 방식뿐입니다.

반복(iteration) 방식 − 함수 내부에 루프(while 문 등)를 사용해 중간 요소와의 일치 여부를 반복적으로 확인합니다.
재귀(recursion) 방식 − 함수가 자기 자신을 서로 다른 매개변수 값으로 계속 호출하며 탐색 범위를 줄여 나갑니다.

방법 1: 반복문을 사용한 이진 탐색

#include <stdio.h>

int iterativeBsearch(int A[], int size, int element);

int main() {
    int A[] = {0, 2, 6, 11, 12, 18, 34, 45, 55, 99};
    int n = 55;
    printf("%d is found at Index %d \n", n, iterativeBsearch(A, 10, n));
    return 0;
}

int iterativeBsearch(int A[], int size, int element) {
    int start = 0;
    int end = size - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (A[mid] == element) {
            return mid;
        } else if (element < A[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

실행 결과

55 is found at Index 8

방법 2: 재귀 호출을 사용한 이진 탐색

#include <stdio.h>

int RecursiveBsearch(int A[], int start, int end, int element) {
    if (start > end)
        return -1;
    int mid = (start + end) / 2;
    if (A[mid] == element)
        return mid;
    else if (element < A[mid])
        return RecursiveBsearch(A, start, mid - 1, element);
    else
        return RecursiveBsearch(A, mid + 1, end, element);
}

int main() {
    int A[] = {0, 2, 6, 11, 12, 18, 34, 45, 55, 99};
    int n = 55;
    printf("%d is found at Index %d \n", n, RecursiveBsearch(A, 0, 9, n));
    return 0;
}

실행 결과

55 is found at Index 8

정리

두 방식 모두 시간 복잡도는 O(log n)으로 동일합니다. 반복 방식은 재귀 호출에 따른 스택 오버플로 위험이 없다는 장점이 있고, 재귀 방식은 코드가 간결해 탐색 논리를 직관적으로 표현할 수 있습니다. 단, 어떤 방식을 사용하든 이진 탐색이 정확히 동작하려면 탐색 대상 배열이 반드시 오름차순으로 정렬되어 있어야 한다는 점을 잊지 말아야 합니다.