이진 검색 알고리즘을 사용한 C 언어 예제

6/29/2023
3 minutes to read

이진 검색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾을 수 있는 효율적인 알고리즘입니다. 이번 포스트에서는 C 언어를 사용하여 이진 검색 알고리즘을 구현한 예제를 살펴보겠습니다.

코드: binary_search_example.c

#include <stdio.h>
#include <stdlib.h>
#include <search.h>

// 정수 비교를 위한 사용자 정의 함수
int compare_integers(const void* value1, const void* value2)
{
    return (*(int*)value1 - *(int*)value2);
}

// 배열 출력을 위한 함수
void print_array(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void)
{
    int search_key = 5; // 찾고자 하는 값
    int* found_value; // 검색 결과를 저장할 포인터
    int numbers[5] = { 45, 12, 5, 89, 27 }; // 검색 대상 배열

    printf("정렬 전: ");
    print_array(numbers, 5); // 정렬 전 배열 출력

    // 배열을 오름차순으로 정렬
    qsort(numbers, 5, sizeof(numbers[0]), compare_integers);

    printf("정렬 후: ");
    print_array(numbers, 5); // 정렬 후 배열 출력

    // 이진 검색 수행 (찾고자 하는 값, 배열, 배열 크기, 배열 원소 크기, 비교 함수)
    found_value = bsearch(&search_key, numbers, 5, sizeof(numbers[0]), compare_integers);

    // 검색 결과 출력
    if (found_value)
    {
        printf("%d를 %ld번 위치에서 찾았습니다.\n", search_key, found_value - numbers);
    }
    else
    {
        printf("%d를 찾지 못했습니다.\n", search_key);
    }

    return 0;
}

정렬 전: 45 12 5 89 27
정렬 후: 5 12 27 45 89
5를 0번 위치에서 찾았습니다.

이 예제에서는 이진 검색 알고리즘을 사용하여 정렬된 배열에서 원하는 값을 찾습니다. 먼저, 정수를 비교하는 사용자 정의 함수 compare_integers를 작성합니다. 이 함수는 qsort와 bsearch 함수에서 사용됩니다.

다음으로, 배열을 출력하는 print_array 함수를 작성합니다. 이 함수는 배열의 요소를 출력하고, 줄바꿈 문자를 추가합니다.

main 함수에서는 다음과 같은 작업을 수행합니다:

찾고자 하는 값을 정의합니다.
검색 대상이 되는 배열을 정의합니다.
배열을 정렬합니다. 이진 검색은 정렬된 배열에서만 작동하므로, 배열을 먼저 정렬해야 합니다.
이진 검색을 수행합니다. bsearch 함수는 찾고자 하는 값, 배열, 배열 크기, 배열 원소 크기, 비교 함수를 인자로 받습니다. bsearch는 검색에 성공하면 찾은 값을 가리키는 포인터를 반환하고, 실패하면 NULL을 반환합니다.
검색 결과를 출력합니다. found_value 포인터가 NULL이 아닌 경우, 찾은 값을 출력하고, 그 위치를 계산하여 출력합니다. NULL인 경우, 원하는 값을 찾지 못했음을 출력합니다.

이 예제를 통해 이진 검색 알고리즘을 사용하여 정렬된 배열에서 원하는 값을 빠르게 찾는 방법을 이해할 수 있습니다. 이진 검색 알고리즘은 효율적이고 빠른 검색 방법으로, 컴퓨터 과학 및 프로그래밍에서 널리 사용되는 기초 알고리즘 중 하나입니다.