참고 유튜브 및 Github : 나동빈 님
유튜브 : https://youtu.be/94RC-DsGMLo
Github : https://github.com/ndb796/python-for-coding-test/blob/master/15/1.java
// 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
public static int countByRange(int[] arr, int leftValue, int rightValue) {
// **유의: lowerBound와 upperBound는 end 변수의 값을 배열의 길이로 설정**
int rightIndex = upperBound(arr, rightValue, 0, arr.length);
int leftIndex = lowerBound(arr, leftValue, 0, arr.length);
return rightIndex - leftIndex;
}
public static int lowerBound(int[] arr, int target, int start, int end) {
while (start < end) {
int mid = (start + end) / 2;
if (arr[mid] >= target) end = mid;
else start = mid + 1;
}
return end;
}
public static int upperBound(int[] arr, int target, int start, int end) {
while (start < end) {
int mid = (start + end) / 2;
if (arr[mid] > target) end = mid;
else start = mid + 1;
}
return end;
}