C 언어 이진 검색 완벽 가이드: 배열에서 최솟값 찾는 방법과 예제 코드

C 언어의 두 가지 검색 기법

C 프로그래밍 언어는 대표적으로 두 가지 검색 기법을 제공합니다.

선형 검색(Linear Search) − 처음부터 끝까지 요소를 하나씩 순서대로 확인하는 방식
이진 검색(Binary Search) − 탐색 범위를 절반씩 줄여가며 빠르게 찾아내는 방식

이진 검색이란?

이진 검색은 정렬된 리스트에만 적용할 수 있다는 전제 조건을 가진 고속 탐색 알고리즘입니다. 동작 과정은 다음과 같습니다.

주어진 리스트를 두 개의 동일한 부분으로 나눕니다.
찾으려는 키(key) 값을 리스트의 중간 요소와 비교합니다.

비교 결과에 따라 세 가지 상황 중 하나가 발생합니다.

중간 요소가 키와 일치하면 → 검색이 성공적으로 종료됩니다.
중간 요소가 키보다 크면 → 왼쪽 절반에서 검색을 계속 진행합니다.
중간 요소가 키보다 작으면 → 오른쪽 절반에서 검색을 계속 진행합니다.

입력(Input) − 요소들의 리스트, 찾고자 하는 키 값

출력(Output)

성공(Success) − 키를 찾은 경우
실패(Unsuccessful) − 키를 찾지 못한 경우

탐색 범위의 중간 위치(mid)는 아래 수식으로 계산합니다.

key = 20
mid = (low + high) / 2

프로그램 1: 이진 검색 기본 구현

다음은 이진 검색 알고리즘을 직접 구현하여 배열에서 특정 키 값을 찾는 C 프로그램입니다. 저점(low)과 고점(high) 사이의 중간 요소를 반복적으로 비교하면서 탐색 범위를 좁혀 나갑니다.

#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;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Run 1:
enter the no: of elements:5
enter the elements:
12
34
11
56
67
enter a key element:45
search is unsuccessful
Run 2:
enter the no: of elements:3
enter the elements:
12
34
56
enter a key element:34
search is successful

첫 번째 실행에서는 키 값 45가 배열에 없어 검색에 실패했고, 두 번째 실행에서는 키 값 34를 성공적으로 찾아냈습니다.

프로그램 2: 최소 힙을 활용한 배열의 최솟값 찾기

아래는 배열에서 최소 요소를 찾는 또 다른 C 프로그램입니다. 이 프로그램은 Bmin 함수를 통해 배열을 최소 힙(min-heap) 구조로 재배열한 뒤, 힙의 루트에 위치하는 최솟값을 반환하는 방식으로 동작합니다.

#include <stdio.h>
void Bmin(int *a, int i, int n){
    int j, temp;
    temp = a[i];
    j = 2 * i;
    while (j <= n){
        if (j < n && a[j+1] > a[j])
            j = j + 1;
        if (temp < a[j])
            break;
        else if (temp >= a[j]){
            a[j / 2] = a[j];
            j = 2 * j;
        }
    }
    a[j/2] = temp;
    return;
}
int binarysearchmin(int *a,int n){
    int i;
    for(i = n/2; i >= 1; i--){
        Bmin(a,i,n);
    }
    return a[1];
}
int main(){
    int n, i, x, min;
    int a[20];
    printf("Enter no of elements in an array\n");
    scanf("%d", &n);
    printf("\nEnter %d elements: ", n);
    for (i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    min = binarysearchmin(a, n);
    printf("\nminimum element in an array is : %d", min);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Enter no of elements in an array
5
Enter 5 elements:
12
23
34
45
56
minimum element in an array is: 12

입력한 5개의 요소 중 가장 작은 값인 12가 올바르게 출력되는 것을 확인할 수 있습니다.

핵심 정리

이진 검색은 정렬된 데이터에서만 동작하며, 시간 복잡도는 O(log n)으로 선형 검색(O(n))보다 훨씬 효율적입니다.
탐색 범위를 매번 절반으로 줄이는 방식이므로 데이터가 클수록 그 성능 차이가 더욱 커집니다.
힙 구조를 활용하면 정렬 없이도 배열의 최솟값을 효율적으로 구할 수 있습니다.