2. 정렬된 배열에서 특정 원소의 개수 구하기

• 코딩테스트에서는 정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산하는 것을 요구하는 경우가 종종 있다.
• 이러한 문제를 해결하기 위해 lowerBound() 함수와 upperBound()함수를 사용할 수 있다.
• lowerBound(arr,x): 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 왼쪽 인덱스 반환 => 하한선을 구함
• upperBound(arr,x):정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 오른쪽 인덱스를 반환 => 상한선을 구함
• upperBound-lowerBound = 특정 점위에 해당하는 원소의 개수

1. 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
}

2.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 // 최대한 오른쪽으로 이동하기
    }
}

3.countByRange()

function countByRange(arr,leftValue,rightValue){
    let rightIndex=upperBound(arr,rightValue,0,arr.length)
    let leftIndex=lowerBound(arr,leftValue,0,arr.length);
    return rightIndex-leftIndex
}