이진 탐색 - Lower_bound & Upper_bound

Lower_bound 

Lower_bound는 하한선 이라는 뜻이다.

찾고자 하는 Key 값 보다 크거나 같은 첫 번째 인덱스를 찾아주는 알고리즘이다.

이를 활용하면 원하는 Key 값이 없어도 이에 가장 가까운 데이터의 위치를 찾을 수 있다.

Lower_bound는 Key 값보다 크거나 같은 원소의 위치(이상)를 찾는 것이기 때문에

mid의 값이 Key보다 작을 때는 left를 mid + 1로 변경해 주고 ( if( arr[mid] < Key)  left = mid +1 )

Key보다 크거나 같을 때는 right를 mid로 변경하여 ( else right = mid ) 

Key 값을 포함시키도록 한다.

---

Lower_bound : 일치하는 숫자가 처음 나타나는 지점

public class Lower_bound {

	public static void main(String[] args) {
		int arr[] = {1,3,3,5,7,9};
		System.out.println(lowerBound(7, 0, arr.length-1, arr));
	}

	static int lowerBound(int key, int left,int right ,int[] arr){
		// key : 구하고자 하는 값
		// left : 왼쪽 끝 인덱스  / 0
		// right : 오른쪽 끝 인덱스  / arr.length-1
		// arr : 배열
		int mid; // 중간값
		while(left < right){
			mid = (left + right) / 2; // 중간값 구하기
			if(arr[mid] < key){ // 배열의 중간값보다 구하고자 하는 값이 클 경우
				left = mid + 1; // 왼쪽 끝 인덱스에 중간값 + 1
			} else {
				right = mid; // 작은경우 오른쪽 끝 인덱스에 중간값
			}
		}
		return right;
	};
}

---

Upper_bound

Upper_bound는 상한선이라는 뜻이다.

찾고자 하는 Key 값보다 큰 첫번째 인덱스를 찾아주는 알고리즘이다.

Upper_bound는 Key 값보다 큰 원소의 위치(초과)를 찾는 것이기 때문에

mid의 값이 Key 값보다 작거나 같을 때는 left를 mid + 1 로 변경 해주고 

Key보다 클 때는 right를 mid로 변경하여 Key 값을 포함시키도록 한다.

즉, Key를 찾아도 left를 증가 시켜준다.

---

Upper_bound : 일치하는 숫자 다음 수 나타나는 지점

public class Upper_bound {
	public static void main(String[] args) {
		int arr[] = {1,3,3,5,7,9};
		System.out.println(upperBound(3, 0, arr.length-1, arr));
	}

	static int upperBound(int key, int left,int right, int[] arr){
		// key : 구하고자 하는 값
		// left : 왼쪽 끝 인덱스  / 0
		// right : 오른쪽 끝 인덱스  / arr.length-1
		// arr : 배열
		int mid; // 중간값
		while(left < right){
			mid = (left + right) / 2; // 중간값 구하기
			if(arr[mid] <= key){ // 배열의 중간값보다 구하고자 하는 값이 크거나 같은경우
				left = mid + 1; // 왼쪽 끝 인덱스에 중간값 + 1
			} else {
				right = mid; // 작은경우 오른쪽 끝 인덱스에 중간값
			}
		}
		return right;
	}
}