이진 탐색 (Binary Search)

2026. 07. 29

들어가는 말

이진 탐색은 정렬된 데이터에서 탐색 범위를 절반씩 줄여 가며 원하는 값의 위치를 찾는 알고리즘이다.

먼저 탐색 범위의 중앙에 있는 값과 찾으려는 값을 비교한다.
오름차순으로 정렬된 배열에서 중앙값이 찾는 값보다 작으면 찾는 값이 중앙값의 오른쪽에 있다는 의미다.
따라서 중앙값과 그 왼쪽 구간을 탐색 대상에서 제외하고 오른쪽 구간만 탐색한다.

이처럼 탐색 범위를 반복해서 절반으로 줄이기 때문에 이진 탐색이라고 부른다.
정렬된 원소가 n개일 때 시간 복잡도는 O(log n)이다.

탐색 과정 살펴보기

탐색에 성공하는 경우

오름차순으로 정렬된 다음 배열에서 값 7의 인덱스를 찾아보자.

Value:  1  2  3  4  5  6  7
Index:  0  1  2  3  4  5  6

배열의 원소가 7개일 때 $\log_2 7 \approx 2.81$ 이며, 이를 올림하면 3이다.
따라서 값 7을 찾기 위해 총 3회차의 탐색을 진행한다.

처음에는 배열 전체가 탐색 범위이므로 left는 시작 인덱스 0, right는 마지막 인덱스 6으로 정한다.
탐색이 진행되어 범위가 줄어들면 새로운 탐색 범위에 맞게 left와 right의 값도 변경된다.
mid는 현재 탐색 범위의 중앙 인덱스이며, (left + right) / 2로 구한다.
arr[mid]는 중앙 인덱스에 저장된 값으로, 찾으려는 값과 비교하는 대상이다.

회차	`left`	`right`	`mid`	`arr[mid]`	비교	처리
1	0	6	3	4	`4 < 7`	`left`를 `mid + 1`인 `4`로 변경
2	4	6	5	6	`6 < 7`	`left`를 `mid + 1`인 `6`으로 변경
3	6	6	6	7	`7 == 7`	인덱스 6을 반환

탐색에 실패하는 경우

오름차순으로 정렬된 다음 배열에서 존재하지 않는 값 8의 인덱스를 찾아보자.

회차	`left`	`right`	`mid`	`arr[mid]`	비교	처리
1	0	6	3	4	`4 < 8`	`left`를 `mid + 1`인 `4`로 변경
2	4	6	5	6	`6 < 8`	`left`를 `mid + 1`인 `6`으로 변경
3	6	6	6	7	`7 < 8`	`left`를 `mid + 1`인 `7`로 변경

3회차가 끝나면 left가 7, right가 6이 되어 시작 인덱스가 마지막 인덱스보다 큰 유효하지 않은 탐색 범위가 된다.
따라서 값을 찾지 못했음을 나타내는 -1을 반환하고 탐색을 종료한다.

소스 코드

반복문을 사용한 이진 탐색

#include <stdio.h>

int binary_search(const int arr[], int size, int target)
{
    int left = 0;
    int right = size - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
            return mid;

        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

int main(void)
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int index = binary_search(arr, size, target);

    if (index != -1)
        printf("%d is at index %d.\n", target, index);
    else
        printf("%d was not found.\n", target);

    return 0;
}

재귀를 사용한 이진 탐색

#include <stdio.h>

int binary_search_recursive(const int arr[], int left, int right, int target)
{
    if (left > right)
        return -1;

    int mid = (left + right) / 2;

    if (arr[mid] == target)
        return mid;

    if (arr[mid] < target)
        return binary_search_recursive(arr, mid + 1, right, target);

    return binary_search_recursive(arr, left, mid - 1, target);
}

int binary_search(const int arr[], int size, int target)
{
    return binary_search_recursive(arr, 0, size - 1, target);
}

int main(void)
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int index = binary_search(arr, size, target);

    if (index != -1)
        printf("%d is at index %d.\n", target, index);
    else
        printf("%d was not found.\n", target);

    return 0;
}