[탐색] 이진 탐색(Binary Search)

작성일 | In

이진탐색이란?

순차 탐색은 배열의 길이가 n이라면, 최대 n번 계산해야 해를 구할 수 있습니다.
이번에 다룰 이진탐색은 특정 조건만 만족하면 순차 탐색보다 훨씬 더 빠르게 해를 구할 수 있습니다.

이 알고리즘이 이진탐색이라고 불리는 이유는 탐색을 할 때 탐색 범위를 1/2씩 줄여나가기 때문에 이진탐색 또는 이분탐색이라 불립니다.

위에서 말한 특정조건은 “정렬된 데이터 집합” 입니다.

수행 과정을 살펴보자면,

  1. 데이터 집합에서 중앙에 있는 값을 선택합니다.
  2. 선택한 값과 찾고자 하는 값을 비교합니다.
  3. 비교 결과를 적절히 활용하여 탐색 범위를 변경합니다.
  4. 목표값이 더 작다면 탐색 범위의 끝을 중앙-1 로 바꿔서 탐색 범위를 중앙값의 왼쪽부분으로 지정합니다.
  5. 목표값이 더 크다면 탐색 범위의 시작을 중앙+1 로 바꿔서 탐색범위를 중앙값의 오른쪽 부분으로 지정합니다. 예를 들자면,

{1, 3, 5, 6, 10, 13, 29, 31, 32} 가 있고, 13을 찾으려고 합니다.
먼저, 중앙값을 뽑으면, 10 입니다. 13은 10보다 크니까 탐색 범위를 13 ~ 32 로 바꿉니다.
13~32에서 중앙값을 뽑으면 29입니다. 13은 29보다 작으니까 탐색 범위를 13~13으로 바꿉니다.
13~13의 중앙값은 13이고, 찾으려고 하는 수와 같으므로 탐색이 종료됩니다.

시간 복잡도 분석

순차탐색은 배열의 길이가 n일때 최대 n번 계산해야 해를 구할 수 있었습니다. 그러면, 이진탐색은 몇 번 계산해야 하는지 알아봅시다.
첫 탐색때 탐색 범위는 전체의 1/2가 됩니다.
두번째 탐색때는 전체의 1/4
세번째 탐색때는 전체의 1/8 …
처럼 되는데 여기서 규칙이 보입니다.
데이터의 개수를 n, 탐색 반복 횟수를 x라 하면

1 = n * (1/2)^x
가 됩니다.
(1/2)^x는 1/(2^x) 와 같기 때문에 식은 다음과 같이 바꿀 수 있습니다.

  • 1 = n * 1/(2^x)
  • n = 1 / (2^x)
  • 2^x = n
    이 되고, log를 이용해 표현하면
    x = log2n 이 됩니다.

즉, 이진탐색의 반복횟수는 log2n입니다.

만약 문제에서 데이터의 수가 10억이라고 가정해봅시다.
순차탐색을 쓰면 보통 시간 초과 가 뜹니다. 그러나 이진탐색을 쓰면 약 30번만 계산하기 때문에 제한 시간 안에 풀 수 있습니다.

구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#define N 10

int main(){
    int arr[N]={2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int front=0, rear=N-1, mid, find;
    scanf("%d", &find);
    while(front<=rear){
        mid=(front+rear)/2;
        if(arr[mid]==find){
            printf("arr[%d]", mid);
            return 0;
        }
        if(arr[mid]<find){
            front=mid+1;
        }
        if(find<arr[mid]){
            rear=mid-1;
        }
    }
    printf("Not Exist");
}