이분 탐색(Binary Search)

이분 탐색(Binary Search)이란 특정 값을 비교적 빠르게 찾는 알고리즘입니다.

 

선형 탐색의 경우 N개 값 중에 T라는 값을 찾는다면 최악의 경우 O(N)의 시간 복잡도를 가집니다.

 

하지만 이분 탐색은 최악의 경우 O(logN)의 시간 복잡도를 가집니다.

 

이분 탐색은 1가지 조건이 필요합니다.

 

• 입력받은 값들이 정렬되어 있어야합니다.  

이분 탐색은 특정 값을 찾을 때 탐색 범위를 절반씩 나눠가며 값을 찾는데, 이때 절반으로 나누는 기준이 값의 크기입니다. 크기에 따라 나누어진 절반의 오른쪽 범위인지, 왼쪽 범위인지를 구별합니다.

 

이분 탐색의 기본 로직은

1. 처음에 Left, Right 값을 인덱스의 시작, 끝으로 초기화한다.
2. Left, Right의 중간 위치의 값이 찾는 값 T보다 크면 Left를 중간 다음 위치로, 작으면 Right를 중간 이전 위치로 값을 정한다
3. 2번의 과정을 값을 찾을 때까지 반복한다.

#include <stdio.h>

int main(void)
{
    int T;
    int result = 0;

    int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 };

    scanf("%d", &T);
    int left = 0, right = 9;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (a[mid] > T)
            right = mid - 1;
        else if (a[mid] < T)
            left = mid + 1;
        else
        {
            result = mid;
            break;
        }
    }

    printf("%d\n", result);

    return 0;
}

 

위 과정을 통해서 탐색을 하면 탐색 범위는

 

(1 / 2)^K * N  (K는 탐색 횟수)

 

만큼 작아질 것이며, K ≈ logN이 된다.

 

즉, 시간 복잡도는 O(logN)이 된다.