[알고리즘] 이분 탐색(Binary Search)

이분 탐색이란 주어진 데이터 중에서 원하는 데이터를 찾는 탐색 기법 중 하나로, 전체 범위를 두 부분으로 나누는 과정을 반복하여 목표값을 찾아내는 기법이다. 간단하게 예를 들면, 레크레이션 등에서 많이 하는 업다운(Up, Down) 게임을 생각하면 된다. 1~100 숫자 중 사회자가 생각한 숫자를 맞출 때 중간값인 50을 처음 부르고 이후 사회자의 Up, Down 대답에 따라 75, 25 등 나머지 범위의 중간값을 계속 부르는 방식으로 진행된다.

진행 순서

1. 초기 설정 (left = 최소 index 값, right = 최대 index 값)
2. mid 값 설정 (left : 최소 index 값, right : 최대 index 값, mid = (left+right)/2 )
   • 이분 탐색을 적용하기 위해서는 데이터가 이미 정렬이 된 상태여야 한다.
3. mid 값과 dest(목표값) 비교
   • mid == dest : 탐색 완료 (종료)
   • mid > dest : right = mid - 1
   • mid < dest : left = mid + 1
4. left > right 가 될 때까지 2 ~ 4 과정 반복

 

구현

int binarySearch(vector<int> numbers, int dest){
    int left, right, mid;

    left = 0;
    right = numbers.size() - 1;
    
    while(left <= right){
        mid = (left + right) / 2
        
        if(numbers[mid] == dest) return mid;
        else if(numbers[mid] > dest) right = mid - 1;
        else left = mid + 1;
    }

    return -1;	// 탐색 실패
}