lowerBound(arr,x)
정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 왼쪽 인덱스를 반환
upperBound(arr,x)
정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 오른쪽 인덱스를 반환
const 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;
};
const upperBound = (arr, target, start, end) => {
while (start < end) {
let mid = parseInt((start + end) / 2);
if (arr[mid] <= target) start = mid + 1;
else end = mid;
}
return start;
};
const countByRange = (arr, leftValue, rightValue) => {
let rightIndex = upperBound(arr, rightValue, 0, arr.length - 1);
let leftIndex = lowerBound(arr, leftValue, 0, arr.length - 1);
return rightIndex - leftIndex;
};
let target = 3;
let arr = [1, 2, 2, 2, 3, 4];
console.log(countByRange(arr, target, target)); //1
console.log(countByRange(arr, -1, 2)); //4
'알고리즘' 카테고리의 다른 글
[JS 알고리즘] 순차 탐색과 이진 탐색 (1) | 2023.12.26 |
---|---|
[JS 알고리즘] 백준 17609 (0) | 2023.12.07 |
[js 알고리즘] 백준 9009: 피보나치 (0) | 2023.11.28 |
[JS 알고리즘] 병합 정렬이란? (0) | 2023.11.22 |
[JS알고리즘] 선택 정렬, 버블 정렬, 삽입 정렬 (2) | 2023.11.22 |