[리트코드] 35. Search Insert Position

 

var searchInsert = function(nums, target) {
    let left = 0,
        right = nums.length - 1,
        cnt = 0

    while(left <= right){
        let mid = parseInt((left + right) / 2)
        if(nums[mid] === target) return mid
        if(nums[mid] < target){
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    for(let val of nums){
        if(val < target){
            cnt++
        }
        if(target > nums[nums.length - 1]) {
            return nums.length
        } 
    }
    return cnt
};

이진 탐색을 하면서 값이 있다면 mid를 리턴하고 그렇지 않다면 몇번째 인덱스에 들어가야 하는지를 묻는 문제

배열이 정렬되어 있기 때문에 nums[nums.length - 1]이 가장 큰 값 입니다. 큰 값보다 target이 클 때는 배열의 길이를 리턴해주었습니다.

 

하지만 반복문을 두번이나 돌려주는 것은 좋지 않은 것 같아 좀 더 최적화를 해봤습니다.

var searchInsert = function(nums, target) {
    let left = 0,
        right = nums.length - 1,
        mid = parseInt((left + right) / 2)

    while(nums[mid] !== target && left <= right){
        if(nums[mid] === target) return mid
        if(nums[mid] < target){
            left = mid + 1
        } else {
            right = mid - 1
        }
        mid = parseInt((left + right) / 2)
    }

    return nums[mid] === target ? mid : left;
};