[알고리즘][탐색][C/C++] Lower Bound, Upper Bound

---

 

Lower Bound, Upper Bound 특징

1. Lower Bound : 원하는 값 k 이상이 처음 나오는 위치를 찾기
2. Upper Bound : 원하는 값 k 초과가 처음 나오는 위치를 찾기
3. Binary Search (= 원하는 값 k의 위치 찾기)에서 파생된 index search 알고리즘
4. 시간복잡도 : O(logN)

 

 

 

 

 

Lower Bound, Upper Bound 과정 이해하기

이 2가지 알고리즘의 결과는 아래 그림처럼 표현할 수 있다. 

 

K=2 일 때, Lower Bound & Upper Bound

 

 

 

 

 

그렇다면, 위의 결과를 어떻게 구현할 수 있을까? 먼저 Lower Bound 구현 과정을 확인해보자. 

[ Lower Bound 과정 ]

1. 배열의 처음과 끝을 각각 s와 e로 설정한다. 
2. s와 e의 중간인 mid index를 계산한다. 
3 - ①. K <= A[mid] 인경우, e를 mid 위치로 이동한다. 
3 - ②. K > A[mid] 인 경우, s를 (mid + 1) 위치로 이동한다. 
4. s < e 가 만족하는 동안, 반복한다. 
5. s위 위치가 Lower Bound 이다. 

 

 

 

K <= A[mid] 이므로, e를 mid 위치로 이동

 

K > A[mid] 이므로, s를 (mid + 1) 위치로 이동

 

K <= A[mid] 이므로, e를 mid 위치로 이동

 

s < e 조건을 만족하지 않으므로, 반복 종료

 

 

 

 

 

Upper Bound 구현은 Lower Bound 과정에서 "=" 만 바꾸면 쉽게 구현할 수 있다. 

[ Uppper Bound 과정 ]

1. 배열의 처음과 끝을 각각 s와 e로 설정한다.
2. s와 e의 중간인 mid index를 계산한다.
3 - ①. K < A[mid] 인경우, e를 mid 위치로 이동한다.
3 - ②. K >= A[mid] 인 경우, s를 (mid + 1) 위치로 이동한다.
4. s < e 가 만족하는 동안, 반복한다. 
5. s의 위치가 Upper Bound 이다. 

 

 

 

---

 

Lower Bound 코드

int lowerBound(int k) {
	int s = 0, e = N - 1, mid;

	while (s < e) {
		mid = (s + e) / 2;
		if (k <= A[mid]) e = mid;
		else s = mid + 1;
	}
	return s;
}

 

 

 

Upper Bound 코드

int upperBound(int k) {
	int s = 0, e = N - 1, mid;

	while (s < e) {
		mid = (s + e) / 2;
		if (k < A[mid]) e = mid;
		else s = mid + 1;
	}
	return s;
}

 

---

 

연습문제 추천

[Pro][삼성] 15942번 : 외계인 침공 - 1

[Pro][삼성] 15942번 : 외계인 침공 - 1