이분 탐색(Binary Search)

이분 탐색이란?

이분 탐색(Binary Search)는 오름차순 혹은 내림차순으로 정렬된 수열에서 검색하는 알고리즘이다. 선형 탐색보다 훨씬 빠르게 탐색할 수 있다는 장점이 있다. 시간복잡도는 탐색할 범위를 절반으로 줄여서 탐색하므로 O(logn)이다.

이분 탐색은 아래와 같은 과정으로 이루어진다.

1. 배열의 가운데 요소의 인덱스를 pivot으로 정한다.

2. a[pivot]의 값이 찾고자 하는 요소와 같다면 검색완료

3. a[pivot]의 값이 찾는 값보다 크다면 left ~ pivot 사이를 탐색한다.

4. a[pivot]의 값이 찾는 값보다 작다면 pivot ~ right 사이를 탐색한다.

아래의 수열에서 이분탐색으로 80을 찾아보자

pivot = (left+right)/2 이다.

left = 0, right = 9, pivot = (0+9)/2 = 4 이다.
a[4] = 45 < 80 보다 작으므로 80은 pivot의 오른쪽에 있을 것이 자명하다.

left = pivot+1 = 5, right = 9, pivot = (5+9)/2 = 7
a[7] = 72 < 80

left = pivot+1 = 8, right = 9, pivot = (8+9)/2 = 8
a[8] = 80 == 80

이므로 3번만에 80을 찾을 수 있다.

코드

#include <iostream>
 
using namespace std;
 
int main(void)
{
    int a[10] = { 2, 17, 19, 21, 45, 50, 55, 72, 80, 120 };
    int key;
    cin >> key;
 
    int left = 0;
    int right = 9;
    bool flag = false;
    while (left <= right) {
        cout << "left: " << left << ",right: " << right << endl;
        int pivot = (left + right) / 2;
        if (a[pivot] == key) {	
            flag = true;
            cout << pivot <<  endl;
            break;
        }
        else if (a[pivot] < key) {
            left = pivot + 1;
        }
        else {
            right = pivot - 1;
        }
    }
 
    if (!flag) {
        cout << "검색 실패" << endl;
    }
    
    return 0;
}

실행결과

• key가 21일때
  
• key가 20일때