[C] 이진 탐색 알고리즘 Binary Search Algorithm

#1. 이진 탐색 알고리즘이란?

이진 탐색 알고리즘 도형화 (wikipeida)

이진 탐색 알고리즘은 정렬된 목록이나 배열 내에서 특정 값을 찾기 위해 일반적으로 사용되는 탐색 알고리즘이에요. 분할정복(divide-and-conquer) 방식을 따르며 검색 공간을 반으로 반복 분할하여 목표 값을 효율적으로 찾아요.

이진 탐색 알고리즘의 작동 방식은 다음과 같아요.

1. 정렬된 목록 또는 요소 배열로 시작해요.
2. 검색 공간의 하한 및 상한을 정의해요. 처음에는 하한이 첫 번째 요소로 설정되고 상한이 마지막 요소로 설정되어요.
3. 하한과 상한의 평균을 취하여 검색 공간의 중간 인덱스를 계산해요.
4. 중간 인덱스에 있는 요소와 대상 값을 비교해요.
5. 목표 값이 중간 요소보다 크면 검색 공간의 위쪽 절반에서 검색이 계속해요. 하한을 중간 인덱스보다 하나 더 많이 업데이트하고 3단계부터 반복해요.
6. 대상 값을 찾거나 검색 공간이 비어 있을 때까지(하한이 상한보다 커짐) 3단계와 4단계를 반복해요.
7. 검색 공간이 비어 있고 대상 값을 찾을 수 없으면 알고리즘이 종료되고 "찾을 수 없음" 표시를 반환해요.

이진 탐색은 시간 복잡도가 O(log n)인 효율적인 알고리즘입니다. 여기서 n은 정렬된 목록 또는 배열의 요소 수입니다. 특히 대규모 데이터 세트의 경우 선형 검색 알고리즘에 비해 필요한 비교 횟수를 크게 줄입니다. 그러나 이진 검색을 사용하려면 사전에 목록을 정렬해야 합니다.

#2. 예제 코드

#include <stdio.h>

/* 이진 탐색 함수 */
int binarySearch(int arr[], int n, int target) 
{
    int start = 0;
    int end = n - 1;
    int mid;

    while (start <= end) 
    {
        mid = (start + end) / 2;

        if (arr[mid] == target) 
        {
            return mid;
        }
        else if (arr[mid] > target) 
        {
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }

    return -1; // 찾는 값이 없으면 -1 반환
}

int main() 
{
    int arr[1000];

    // 1부터 1000까지의 자연수로 배열 초기화
    for (int i = 0; i < 1000; i++) 
    {
        arr[i] = i + 1;
    }

    int target = 10;
    int result = binarySearch(arr, 1000, target);

    if (result == -1) 
    {
        printf("찾는 값이 배열에 없습니다.\n");
    }
    else 
    {
        printf("%d은(는) arr[%d]에 있습니다.\n", target, result);
    }

    return 0;
}