JavaScript: 정렬된 배열에서 값이 삽입되어야 할 가장 낮은 인덱스 구하기 (오름차순·내림차순)

배열(첫 번째 인수)이 오름차순 또는 내림차순으로 정렬된 상태에서, 특정 값(두 번째 인수)이 삽입되어야 할 가장 낮은 인덱스를 반환하는 함수를 작성해 보겠습니다. 반환값은 반드시 숫자여야 합니다.

문제 이해하기

예를 들어 getIndexToInsert()라는 함수가 있다고 가정해 보겠습니다.

getIndexToInsert([1,2,3,4], 1.5, 'asc') → 1
// 1.5는 1(인덱스 0)보다 크지만 2(인덱스 1)보다 작기 때문입니다.

마찬가지로,

getIndexToInsert([20,3,5], 19, 'asc') → 2
// 배열을 오름차순으로 정렬하면 [3,5,20]이 되며,
// 19는 20(인덱스 2)보다 작고 5(인덱스 1)보다 크기 때문입니다.

핵심 아이디어는 간단합니다. 배열 전체를 순회하면서 목표 값보다 작은 요소의 개수를 세면, 그 개수가 곧 삽입되어야 할 인덱스가 됩니다. 내림차순의 경우에는 반대로 목표 값보다 큰 요소의 개수를 세면 됩니다.

구현 예제

const arr = [20, 3, 5];
const getIndexToInsert = (arr, element, order = 'asc') => {
    const creds = arr.reduce((acc, val) => {
        let { greater, smaller } = acc;
        if(val < element){
            smaller++;
        }else{
            greater++;
        };
        return { greater, smaller };
    }, {
        greater: 0,
        smaller: 0
    });
    return order === 'asc' ? creds.smaller : creds.greater;
};
console.log(getIndexToInsert(arr, 19, 'des'));
console.log(getIndexToInsert(arr, 19));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

1
2

코드 설명

reduce() 메서드를 사용해 배열을 한 번만 순회하면서 목표 값보다 작은 요소(smaller)와 그렇지 않은 요소(greater)의 개수를 동시에 집계합니다. 오름차순('asc')일 때는 smaller 값을, 내림차순('des')일 때는 greater 값을 반환하여 삽입 위치를 결정합니다. 세 번째 인수를 생략하면 기본값인 'asc'가 적용됩니다. 이 방식은 배열을 실제로 정렬하지 않고도 O(n) 시간 복잡도로 삽입 인덱스를 계산할 수 있어 효율적입니다.