Binary Search - 이진 탐색 기법과 Lower/Upper bound

오름차순으로 정렬된 배열이 있다고 할 때 

이 배열에서 원하는 값을 찾으려고한다.

 

 

얼마만에 찾을 수 있을까?

 

 

처음 값부터 끝 값까지 순차적으로 탐색한다고 했을 때,

경우를 나누어 보면 다음과 같을 것이다.

 

      1. 최선: 원하는 값이 배열의 맨 앞에 있음

      2. 최악: 원하는 값이 배열의 맨 끝에 있음

      3. 평균: 가운데

 

특히나 배열의 크기가 클 수록 탐색이 어려워질 것이다.

 

 

 

이럴 경우 이진 탐색 기법을 사용하면 효율적으로 원하는 값을 찾을 수 있다.

 

 

 

이진 탐색의 방법은 low와 high를 두고 mid값을 구해서 탐색 범위를 좁혀가는 것이다. 

mid값이 탐색값보다 작다면 low에 mid+1값을 넣어서 다시 탐색을 할 수 있고

mid값이 탐색값보다 크다면 high에 mid-1값을 넣어서 탐색을 하면 된다.

 

 

 

이런 방식으로 탐색을 진행하면 진행할 때마다 탐색할 범위가 반으로 줄어들게 된다.

그래서 탐색에 걸리는 시간은 O(logN)이 된다.

 

 

이는 배열의 크기가 커질수록 순차 탐색과 성능차이가 확연히 다르게 나타날 것이다.

 

 

 

 

이진 탐색의 의사 코드를 대충 작성해보면  다음과 같다.

int BinarySearch(start, end, target, arr[]){
	low = start, high = end
    while(low < high){
    	mid = (low + high)/2
        if(arr[mid] == target) 
        	return mid;
        else if(arr[mid] < target)
        	low = mid + 1;
        else
        	high = mid - 1;
    }
}

 

 

 

 

그런데 만약, 탐색하는 데이터들 중에

동일한 데이터가 여러개가 있다면 어떻게 될까?

 

 

 

찾고자하는 특정 데이터가

몇 번째에 있는 데이터인지 

확신할 수 없을 것이다.

 

 

 

대신 이진 탐색을 이용하면 해당 데이터의 범위는 구할 수 있다.

즉, 이진 탐색을 이용해서 Lower bound, Upper bound를 구할 수 있다.

 

 

이진 탐색을 이용해서 Lower bound를 구하는 방법은

mid값이 target값보다 크거나 같은 경우 high = mid -1 를 두고 그 이전 값만 탐색하면 될 것이고

mid값이 target값보다 작은 경우에는 low = mid +1 로 두고 mid값의 이후만 탐색하면 될 것이다.

 

Upperbound를 구하는 방법은 반대이다.

 

이에 관한 의사코드를 작성해보면 다음과 같다.

int LowerBound(start, end, target, arr[]){
	ret = -1
    low = start, high = end
    while(low < high){
    	mid = (low + high)/2
        if(arr[mid] >= target){
        	ret = mid
           	high = mid - 1
        }else{
        	low = mid + 1
        }
    }
    return ret
}

int UpperBound(start, end, target, arr[]){
	ret = -1
    low = start, high = end
    while(low < high){
    	mid = (low + high)/2
        if(arr[mid] <= target){
        	ret = mid
            low = mid + 1
        }else{
        	high = mid - 1
        }
    }
    return ret 
}