Lower_bound & Upper_bound 알고리즘

 

최근 leet code의 Longest Increasing Sequence (최장 부분 수열) 알고리즘 문제를 풀다가, 예전에 공부했던 lower_bound, upper_bound 개념과 구현이 기억이 나질 않아... 이번 기회에 정리해 보았습니다 ㅎㅎ 항상 두 개념이 헷갈렸었는데 이번 포스팅을 통해 개념을 계속 기억하길 바라는 마음으로 두 개념 비교 위주로 정리하였습니다.

---

Lower_bound와 Upper_bound 비교

	개념	알고리즘 구현
Lower_bound	특정 k값의 시작 위치(k값보다 크거나 같은 위치)를 찾는 알고리즘 [1, 2, 3, 3, 5, 6, 8]          ^ (lower bound of 3)	1. 배열의 중간값 (mid) 를 가져옵니다. 2. 중간 값과 검색 값(k)를 비교합니다.  - 중간 값 < 검색 값: left를 mid + 1로 변경  - 중간 값 > 검색 값: right를 mid 로 변경  3. left ≥ right가 되면, 이분 탐색을 종료하고, right 값이 lower_bound 가 됩니다.
Upper_bound	특정 k값보다 처음으로 큰 값의 위치를 찾는 알고리즘 [1, 2, 3, 3, 5, 6, 8]                   ^     (upper bound of 3)	1. 배열의 중간값 (mid) 를 가져옵니다. 2. 중간 값과 검색 값(k)를 비교합니다.  - 중간 값 ≤ 검색 값: left를 mid + 1로 변경  - 중간 값 > 검색 값: right를 mid 로 변경   3. left ≥ right가 되면, 이분 탐색을 종료하고, right 값이 lower_bound 가 됩니다.

 

이해를 하자!

 

우선 두 알고리즘 모두 right 값이 우리가 원하는 값입니다. 

그렇다면 right 값은 lower_bound의 경우 목푯값(k) 보다 크거나 같게 되는 것이고, upper_bound의 경우 목표값(k) 보다 큰 값을 가지게 되는 것이겠죠? 따라서, 2번 과정에서 lower_bound는 mid에 존재하는 값이 k보다 크거나 같아야 right 위치를 mid로 옮길 수 있는 것이고, upper_bound는 mid 에 존재하는 값이 k보다 커야 right 위치를 mid로 옮길 수 있는 것입니다! 

 

코드는 아래와 같습니다.

---

public static void main(String[] args) {
	int[] nums = new int[]{1,2,3,3,5,6,8};
	int left = 0, right = nums.length-1;
	int k = 3;
    // lower_bound
	while(left<right){
		int mid = left + (right - left) / 2;

		if(nums[mid] >= k) right = mid;
		else left = mid + 1;
	}
	System.out.println(right); // 2
    
    // upper_bound
    left = 0;
    right = nums.length-1;
    while(left<right){
		int mid = left + (right - left) / 2;

		if(nums[mid] > k) right = mid;
		else left = mid + 1;
	}
    System.out.println(right); // 4
}