이분탐색 추가 - Upper Bound(상한), Lower Bound(하한)

상한 : 찾고자 하는 특정 값을 초과하는 '첫 위치' 반환

하한 : 찾고자 하는 특정 값 이상인 '첫 위치' 반환

-> 중복 값이 있을 때의 활용

 

arr1{1, 2, 2, 2, 3} 일 때 Key 값이 2이고, Upper Bound로 찾는다면 2를 초과되는 처음 위치인 arr[4] = 3인 index 4 반환

Lower Bound로 찾게 된다면 2 이상 위치 중 처음 위치인 arr[1] = 2인 index 1 반환

중복 원소에서 가장 끝 값(가장 오른쪽 값)을 찾고자 한다면 Upper Bound - 1

중복 원소 중 가장 왼쪽 끝 값(가장 왼쪽 값)을 찾고자 한다면 Lower Bound 그대로

 

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;
}

 

예시 - 백준 랜선 자르기 (1654)

// min = 0, max 는 입력받은 LAN선 중 가장 긴 길이를 갖는다.
while (min < max) { 
 
	// 범위 내에서 중간 길이를 구한다.
	mid = (max + min) / 2;
 
	long count = 0;
 
	// 구해진 중간 길이로 잘라서 총 몇 개가 만들어지는지를 구한다.
	for (int i = 0; j < arr.length; i++) {
		count += (arr[i] / mid);
	}
			
	/*
	 *  [upper bound 형식]
	 *  
	 *  mid길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면
	 *  자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
	 *  그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
	 */
	if(count < N) {
		max = mid;
	}
	else {
		min = mid + 1;
	}
	
}

 

 

c++은 라이브러리 제공 - 벡터/배열 오름차순 정렬되어있어야 함

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5

	return 0;
}