[leetcode] 35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

아래 문제가 내가 푼 답이다 (시간복잡도를 고려하지 않고 푼 문제..하지만 문제를 보면 O(log n)으로 풀라고 작성되어있다.)

var searchInsert = function(nums, target) {
    const numsArray = [...nums];
    if (numsArray.indexOf(target) !== -1) {
        return numsArray.indexOf(target)
    }
    
    numsArray.push(target);
    numsArray.sort((a, b) => a - b);
    return numsArray.indexOf(target);
};

 

다른 사람의 풀이를 보자

var searchInsert = function(nums, target) {
    let left = 0, right = nums.length
    while(left < right) {
        const mid = left + Math.floor((right - left) / 2)
        if(nums[mid]===target) {
           return mid
        } else if(nums[mid] > target){
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
};

 

binary search를 활용해 시간복잡도 O(log n)로 풀었다

한번 돌지 않고 일단 포함 되는 index를 mid로 잡고 없으면 index를 하나씩 +1을 한 뒤 index를 리턴하는 방식이다

 

다음번에는 이렇게 풀어봐야지..