[알고리즘] #Search Insert Position

문제 출처: https://leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

문제 해석

중복이 없는 오름차순으로 정렬된 배열과 target이 주어졌을 때, target이 배열 안에 있으면 해당 인덱스를 반환한다.

없으면 배열에 target이 들어갈 위치의 index를 리턴하라.

 

 

풀이

이 문제도 마찬가지로 중간값과 target을 비교해서 구현하면 된다. 대신 target이 배열에 없을 때 넣을 순서도 구해야하는데, 이는 min, max 값을 구해서 넣어주면 된다.

 

var searchInsert = function(nums, target) {
    let minIdx = 0;
    let maxIdx = nums.length-1;

    while(minIdx <= maxIdx) {
        if (minIdx === maxIdx) {
            return nums[minIdx] >= target ? minIdx : minIdx+1
        } else {
            const midIdx = Math.floor((minIdx+maxIdx)/2);
            if (nums[midIdx] < target) {
                minIdx = midIdx + 1
            } else if (nums[midIdx] > target) {
                maxIdx = midIdx > 0 ? midIdx - 1 : midIdx
            } else {
                return midIdx
            }
        }
    }
    return minIdx
};