[탐색] 이분 탐색 Binary Search

이분 탐색 Binary Search

 

이분 탐색의 개념과 특징

이분 탐색(혹은 이진 탐색)은 이미 정렬된 배열에 대해 log₂N의 평균 검색 길이를 갖는 매우 빠르고 간단한 알고리즘이다.

 

기본 알고리즘

1. 구간에 대해 중간값을 우선 검사한다.
2. 중간값보다 작다면 찾는 값은 왼쪽 구간에 있다. (right = mid-1)
3. 중간값보다 크다면 찾는 값은 오른쪽 구간에 있다. (left = mid+1)
4. 중간값과 같다면 종료
5. 구간을 줄여가며 1~3을 반복한다.

 

예제

정렬된 배열에 대해 목표값 9를 찾고자 한다.

Search 1.

left = 0(인덱스 위치)

right = 8

mid = (0+8)/2 = 4

>>7(중간값)은 목표값 보다 작으므로 구간을 오른쪽으로 옮긴다.

>>left = mid + 1

 

Search 2.

left = 5

right = 8

mid = (5+8)/2 = 6

>>10(중간값)은 목표값 보다 크므로 구간을 왼쪽으로 옮긴다.

>>right = mid - 1

 

Search 3.

left = 5

right = 5

mid = (5+5)/2 = 5

>>9(중간값)은 목표값과 동일하므로 탐색을 종료한다.

 

결과 : 선형탐색을 했을 경우 6번이 걸리겠지만, 이분 탐색 결과 3번 만에 목표값을 찾아낼 수 있었다.

 

 

시간 복잡도

평균 : O(log₂N)

 

 

구현(c언어 기반)

#include <stdio.h>
#define SIZE 9
int main() {
    int arr[] = { 1, 2, 4, 5, 7, 9, 10, 12, 14 };
    int left = 0;
    int right = SIZE - 1;
    int key = 9;
 
    //left <= right 일때만 검사한다.
    //목표 값이 배열에 없는 경우는 고려하지 않았다.
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] > key)
            right = mid - 1;
        else if (arr[mid] < key)
            left = mid + 1;
        else {//찾은 경우
            printf("배열에서 %d를 찾았습니다.\n", key);
            break;
        }
    }
    return 0;
}