[알고리즘] 상한가, 하한가 구하기 (이진 탐색 활용)

상한가,하한가 구하기

💡 이진 탐색으로 상한가와 하한가를 구해서 원하는 숫자를 출력하자.
- 백준 10816번-

• ‘중복 원수의 개수’ 를 알아내고 싶을 때, 중복 원소의 왼쪽 끝과 오른쪽 끝의 인덱스를 알아내서 계산하면 된다.
• 이진 탐색 개념을 이용하기에 배열은 사전 정렬 되어있어야 한다.

 

방법

1. 찾으려는 값의 하한선, 상한선을 따로 구할 생각을 하자.
2. 하한선은 찾으려는 값 이상의 값이 나타난 위치다.
3. “이상” 이란 같거나 큰 수를 뜻한다.
4. 상한선은 찾으려는 값의 초과 값이 나타난 위치다.
5. “초과” 란 보다 큰 수를 뜻한다.

 

상한가, 하한가 예시

1. 정렬된 배열에서 ‘숫자 10의 상한가, 하한가를 찾는다.
2. (하한선은 최초 10 이 나오는 위치인 3, 상한선은 10을 넘어서는 최초 위치 6 이 나와야 한다.)

2	3	5	10	10	10	12	16
0	1	2	3	4	5	6	7

💡 검색 범위가 절 반만큼 줄어드는 이진 탐색을 이용해서 하한가와 상한가가 되는 마지노선을 찾아서 반환한다.

• 하한가 찾기 → 상한선을 중간 위치만큼 내리면서 왼쪽으로 범위를 좁힌다.
• 하한가, 가장 처음 값을 찾기 위해서는 하한선(low)가 아닌 상한선(high)이 줄어들면서 찾아야 한다.
• 즉, 중간 값이 <<같거나 큰 값>>에 해당되면 상한선 high 가 왼쪽으로 ← 이동(작아진다고)한다고 단순하게 생각하기!!

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;
		}
 
		//찾는 값이 중간 값 보다 크기 때문에, 범위를 중앙+1값으로 다시 줄어버림 
		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;
		}
 
		//찾는 값이 중간 값 보다 크기 때문에, 범위를 중앙+1값으로 다시 줄어버림 
		else {
			lo = mid + 1;  
		}
 
	}
	return lo;
}