이분탐색 - 상/하한선(lower_bound, upper_bound)

주어진 자료에서 중복되지 않은 값이 주어질 때 그 데이터 내에 특정 값이 존재하는 지 검색하는 방법 중 이분탐색(Binary Search)은 자료를 정렬한 후 분할정복방식으로 데이터를 1/2씩 나누면서 값이 존재하는 지 확인하는 알고리즘을 사용했다.

 

이분탐색이 데이터 내 특정 값을 정확히 찾는 것이라면

lower_bound 와 upper_bound 는 이분탐색 알고리즘에서 약간 변형된 것으로 중복된 자료가 있을 때 유용하게 탐색할 수 있는 알고리즘이다.

 

lower_bound 는 데이터 내 특정 K 값보다 같거나 큰 값이 처음 나오는 위치를 리턴해주고 upper_bound 는 K 값보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘이다.

 

---

이분탐색 코드 구현

int binarySearch(int A[], int size, int key){
	int low = 0;
    int high = size - 1;
    
    while(low <= high){
    	int mid = (low + high) / 2;
        if(A[mid] == key){
        	return mid;
        }
        else if(A[mid] < key){
        	low = mid + 1;
        }
        else{
        	high = mid -1;
        }
    }
    return -1;
}

 

---

 

 

private static int lowerBound(int[] arr, int key) {
	int lo = 0; 
	int hi = arr.length; 
 
	// lo가 hi랑 같아질 때 까지 반복
	while (lo < hi) {
 
		int mid = (lo + hi) / 2; // 중간위치를 구한다.
 
		/*
		 *  key 값이 중간 위치의 값보다 작거나 같을 경우
		 *  
		 *  (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
		 */
		if (key <= arr[mid]) {
			hi = mid;
		}
 
		else {
			lo = mid + 1;
		}
 
	}
	return lo;
}
 
private static int upperBound(int[] arr, int key) {
	int lo = 0; 
	int hi = arr.length; 
 
	// lo가 hi랑 같아질 때 까지 반복
	while (lo < hi) {
 
		int mid = (lo + hi) / 2; // 중간위치를 구한다.
 
		// key값이 중간 위치의 값보다 작을 경우
		if (key < arr[mid]) {
			hi = mid;
		}
		// 중복원소의 경우 else에서 처리된다.
		else {
			lo = mid + 1;
		}
	}
	return lo;
}

 

이를 토대로 하나의 key 값에 대해 lower_bound를 통해 얻어진 값과 upper_bound를 통해 얻어진 값의 차를 구하면 된다.

 

 

 

 

 

 

참고 블로그 : https://jackpot53.tistory.com/33
                    https://st-lab.tistory.com/267