lowerBound() & upperBound()
1. 정렬된 배열에서 특정 원소의 개수 구하기
- 코딩 테스트에서는 정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산하는 것을 종종 요구
- 이러한 문제를 해결하기 위해
lowerBound()
함수와 upperBound()
함수를 사용할 수 있다.
2. 하한선과 상한선 함수
- lowerBound(arr, x) : 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 왼쪽 인덱스를 반환
- upperBound(arr, x) : 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 오른쪽 인덱스를 반환
![](https://velog.velcdn.com/images/sky-pey/post/d12f04be-aa86-453e-aeb0-536a85beb0a6/image.png)
3. lowerBound()
코드 예시
function lowerBound(arr, target, start, end) {
while (start < end) {
let mid = parseInt((start + end) / 2);
if (arr[mid] >= target) end = mid;
else start = mid + 1;
}
return end;
}
![](https://velog.velcdn.com/images/sky-pey/post/d7ca6cd4-c8a4-4ac1-ad35-099217888891/image.png)
4. upperBound()
코드 예시
function upperBound(arr, target, start, end) {
while (start < end) {
let mid = parseInt((start + end) / 2);
if (arr[mid] > target) end = mid;
else start = mid + 1;
}
return end;
}
5. countByRange()
- 정렬된 배열에서 값이 특정 범위에 속하는 원소의 개수를 계산
- 앞서 정의한 lowerBound() 함수와 upperBound() 함수를 이용해 구현할 수 있다.
function countByRange(arr, leftValue, rightValue) {
let rightIndex = upperBound(arr, rightValue, 0, arr.length);
let leftIndex = lowerBound(arr, leftValue, 0, arr.length);
return rightIndex - leftIndex;
}
let arr = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9];
console.log(countByRange(arr, 4, 4));
console.log(countByRange(arr, -1, 3));