Lower bound & Upper bound 개념 및 구현

목차

Lower bound & Upper bound 개념 및 구현

---

Lower bound와 Upper bound는 경곗값을 찾는 알고리즘입니다.

Lower bound와 Upper bound는 이진 탐색을 기반으로 하기 때문에 데이터가 정렬되어 있어야 합니다.

이진 탐색을 기반으로 하기 때문에 두 알고리즘의 시간 복잡도는 O(log n) 입니다. (n: 배열 길이)

 

Lower bound

---

Lower bound는 특정 값의 시작 위치를 찾는 알고리즘입니다.

Lower bound

동작 방식

---

Lower bound의 동작 방식은 다음과 같습니다.

초기에 left는 배열의 시작 위치로 right는 배열의 길이로 셋팅합니다.

1. 배열의 중간 값(mid)을 가져옵니다.
2. 중간 값과 검색 값을 비교합니다.
   • 중간 값이 검색 값보다 작다면 left 값을 mid+1로 합니다.
   • 중간 값이 검색 값보다 크거나 같다면 right값을 mid로 합니다.
3. left ≥ right 일 때까지 1번과 2번을 반복합니다.
4. 반복이 끝나면 right 값이 lower bound가 됩니다.

 

다음은 arr 배열에서 k=3의 lower bound를 찾는 과정입니다.

 

1. mid 값을 구하고 k 값과 비교합니다.

• mid = (left + right)/2 = (0 + 9)/2 = 4

Step 1

2. k값이 arr[mid]값과 같기 때문에 right의 위치를 mid로 변경합니다.

• right = mid = 4

Step 2

3. mid 값을 구하고 k 값과 비교합니다.

• mid = (left + right)/2 = (0 + 4)/2 = 2

Step 3

4. k값이 arr[mid]값보다 크기 때문에 left의 위치를 mid+1로 변경합니다.

• left = mid + 1 = 2 + 1 = 3

Step 4

5. mid 값을 구하고 k값과 비교합니다.

• mid = (left + right)/2 = (3 +3)/2 = 3

Step 5

6. k값이 arr[mid]값과 같기 때문에 right의 위치를 mid로 변경합니다.

• right = mid = 3
• left값이 right 값과 같기 때문에 루프를 종료하고 right값이 lower bound 값이 됩니다.

Step 6

구현

---

다음은 arr배열에서 k값의 lower bound를 찾는 코드입니다.

• 매개변수로 left는 배열의 시작위치 right는 arr의 길이로 받습니다.

def lower_bound(arr, left, right, k):
	while left < right:
		mid = (left + right)//2
		if arr[mid] < k:
			left = mid + 1
		else:
			right = mid

	return right

Upper bound

---

Upper Bound는 특정 k값보다 처음으로 큰 값의 위치를 찾는 알고리즘입니다.

Upper bound

 

동작 방식

---

Upper bound의 동작 방식은 다음과 같습니다.

초기에 left는 배열의 시작 위치로 right는 배열의 길이로 세팅합니다.

1. 배열의 중간 값(mid)을 가져옵니다.
2. 중간 값과 검색 값을 비교합니다.
   • 중간 값이 검색 값보다 작거나 같다면 left 값을 mid+1로 합니다.
   • 중간 값이 검색 값보다 크다면 right값을 mid로 합니다.
3. left ≥ right 일 때까지 1번과 2번을 반복합니다.
4. 반복이 끝나면 right 값이 upper bound가 됩니다.

 

다음은 arr 배열에서 k=3의 upper bound를 찾는 과정입니다.

 

1. mid 값을 구하고 k 값과 비교합니다.

• mid = (left + right)/2 = (0 + 9)/2 = 4

Step 1

2. k값이 arr[mid]값과 같기 때문에 left의 위치를 mid+1로 변경합니다.

• left = mid + 1 = 4 + 1 = 5

Step 2

3. mid 값을 구하고 k 값과 비교합니다.

• mid = (left + right)/2 = (5 + 9)/2 = 7

Step 3

4. k값이 arr[mid]값보다 작기 때문에 right의 위치를 mid로 변경합니다.

• right = mid = 7

Step 4

5. mid 값을 구하고 k 값과 비교합니다.

• mid = (left + right)/2 = (5 + 7)/2 = 6

Step 5

6. k값이 arr[mid]값보다 작기 때문에 right의 위치를 mid로 변경합니다.

• right = mid = 6

Step 6

7. mid 값을 구하고 k 값과 비교합니다.

• mid = (left + right)/2 = (5 + 6) / 2 = 5

Step 7

8. k값이 arr[mid]값과 같기 때문에 left의 위치를 mid+1로 변경합니다.

• left = mid + 1 = 5 + 1 = 6
• left값이 right값과 같기 때문에 루프를 종료하고 right값이 upper bound 값이 됩니다.

Step 8

구현

---

다음은 arr배열에서 k값의 upper bound를 찾는 코드입니다.

• 매개변수로 left는 배열의 시작위치 right는 arr의 길이로 받습니다.

def upper_bound(arr, left, right, k):
	while left < right:
		mid = (left + right)//2
		if arr[mid] <= k:
			left = mid + 1
		else:
			right = mid
		
	return right