[JS 알고리즘] 특정 범위에 해당하는 원소 개수 구하기(lowerBound,upperBound)

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