JavaScript-lowerBound()와 upperBound()를 이용해 특정 범위에 속하는 원소의 개수 구하기

lowerBound()와 upperBound()

정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산할 때에 사용

• lowerBound(arr,x):정렬된 순서를 유지하면서 배열 arr에 x를 넣은 가장 왼쪽 인덱스를 반환
• upperBound(arr,x):정렬된 순서를 유지하면서 배열 arr에 x를 넣은 가장 오른쪽 인덱스를 반환

//정렬된 순서를 유지하면서 배열에 삽입할 가장 왼쪽 인덱스 반환
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;
}

//정렬된 순서를 유지하면서 배열에 삽입할 가장 오른쪽 인덱스 반환
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;
}

countByRange():위의 두 함수를 사용하여 정렬된 배열에서 값이 특정 범위에 속하는 원소의 개수를 계산할 수 있음

//값이 [liftValue, rightValue]인 데이터의 개수를 반환하는 함수
function countByRange(arr,leftValue,rightValue){
	//유의: lowerBound와 upperBound는 end 변수의 값을 배열의 길이로 설정
  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];
//값이 4인 데이터 개수 출력
console.log(countByRange(arr,4,4));
//값이 [-1,3] 범위에 있는 데이터 개수 출력
console.log(countByRange(arr,-1,3));