썸넬 img URL : https://www.inchcalculator.com/confidence-interval-calculator/

🌱 반환값

---

원하는 값을 찾지 못했을 때 -1을 반환하는 이진 탐색과 달리 원하는 값을 초과하는 첫 번째 위치, 원하는 값 이상의 첫 번째 위치를 반환한다.

이렇게 -1이 아닌 어떻게든 적절한 위치를 찾아낸다는 특성 덕분에 주로 특정 값을 배열의 어느 위치에 넣어야 되는지를 탐색할 때 많이 사용함

🌱 정의

---

Upper Bound : Key보다 큰 첫 번째 위치(초과) 반환
Lower Bound : Key보다 크거가 같은 첫 번째 위치(이상) 반환

ex) arr = {1, 3, 3, 5, 7}
key = 3이면
Upper Bound = 3(index), Lower Bound = 1(index)

key = 2이면
Upper Bound = 1(index), Lower Bound = 1(index)

🌱 구현

---

🌿 Upper Bound

public static int upperBound(int arr[], int front, int rear, int key){
	int mid;
	while(front<rear){
		mid = (front + rear) / 2;
		if(arr[mid] <= key) front = mid + 1;
		else rear = mid;
	}
	return rear;
}

key보다 큰 첫 번째 위치를 찾는 것이기 때문에
if(arr[mid] <= key) front = mid + 1; 을 해야 한다.
즉, key 값을 찾았어도 front 값을 증가시킨다는 의미이다.

rear = mid
원래 이진 탐색에선 rear = mid - 1로 mid를 포함하지 않는 방식으로 범위를 조정하였으나, Upper, Lower Bound에선 mid를 포함하여 변경한다.
따라서, 최종 연산 후에는 언제나 결과 값이 rear에 위치하게 되고, 이를 반영하여 return rear를 하는 것이다.

🌿 Lower Bound

public static int lowerBound(int arr[], int front, int rear, int key){
int mid;
	while(front<rear){
		mid = (front + rear) / 2;
		if(arr[mid] < key) front = mid + 1;
		else rear = mid;
	}
	return rear;
}

key 보다 크거가 같은 첫 번째 위치를 찾는 것이기 때문에,
if(arr[mid] < key) front = mid + 1; 이 된다.
즉, 키 값을 찾았을 때를 포함해서 front를 변경하는 것이 아닌, 키 값보다 작을 때만 front를 변경한다.

Reference URL : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=221045300639