이분탐색(Binary Search)

이분탐색이란?

조건 : 정렬된 데이터 

이미 정렬된 데이터를 탐색할 때 사용 할 수 있음.

정렬된 데이터 n개가 있을 때

검색 범위를 반으로 줄이면서, 찾고자 하는 값이 어디에 위치했는지 확인하는 탐색임.

vs 선형탐색?

순차적으로 배열 (길이 n)을 탐색하여 일치하는 값이 나올 때까지 탐색한다.

그러나 시간 복잡도는 Worst O(n) 이기 때문에 좋지 못하다.

 

예시로 9개의 수자가 오름차순으로 정렬되어 있다고 할 때

숫자가 몇번째 위치 했는지 확인할 수 있다.

여기서 42가 몇번째 위치에 있는지 확인을 하면?

0번째 부터 8번째까지 위치해 있다.

그렇게 되면 

수열 ( 배열 ; Array ) 기준으로 

start = 0 

end = 8 = array.size - 1

mid = (start + end) / 2

중간 값(mid)가 찾는 값 42인지 확인한다.

 

Case 1) Array[mid] == 42

위치가 42의 값을 갖는 위치이므로 mid 값을 반환한다.

Case 2) Array[mid] < 42 

인덱스 mid 에 위치한 값이 42보다 작다면

현재 start 부터 mid 사이 [start, mid] 에는 42 가 없다는 의미이므로 

start = mid+1 

start 값을 mid + 1 로 갱신시킨다.

Case 3) Array[mid] > 42

인덱스 mid 에 위치한 값이 42보다 크다면

현재 mid 부터 end 사이 [mid, end] 에는 42가 없다는 의미이므로

end = mid-1

end 값을 mid - 1로 갱신시킨다.

위 그림의 경우는 [Case 2] 인 경우이므로

 

start 값을 갱신시킨다.

start = mid + 1 // 5

end = 8

mid = floor( (5+8) / 2 ) = 6

이므로

다음 시행에서는 

Array[mid] = Array[6] == 42 와 일치하는 [Case 1] 의 경우가 되므로 mid 값을 반환 값 혹은 출력 값으로 준다.

 

혹은 배열 내 찾을 값이 없을 수도 있다.

이 경우 start 가 end 보다 커지는 경우,

혹은 end 값이 start 보다 작아지는 경우인데

위 경우에는 값이 없음(인덱스 값을 출력해야 하므로 -1은 인덱스 상에 없으므로 -1을 반환 혹은 출력)을 알려주면 된다.

vector<int> array;
int binary_search(int input_start, int input_end, int find){
    int s = input_start;
    int e = input_end;
    int mid;
    while(s <= e){
        mid = int( (s + e) / 2 );
        if(array[mid] == find) return mid;
        else if(array[mid] > find) e = mid-1;
        else if(array[mid] < find) s = mid+1;
    }
    return -1;
}

 

0123