[리트코드] 35. Search Insert Position - js (이진탐색)

1. 문제

https://leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

2. 코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let answer = 0;

    if(nums.includes(target)) answer = nums.indexOf(target);
    else{
        for(let i=0;i<nums.length;i++){
            if(nums[i] < target && nums[i+1] > target){
                answer = i+1;
                break;
            }
        }
        if(!answer){
            answer =  nums[0] > target ? answer : nums.length;
        }
    }

    return answer;
};

다른 풀이 방법)

이진 탐색을 활용한 방법도 있다. 위의 코드보다 탐색 횟수를 줄일 수 있는 방법이다.

var searchInsert = function(nums, target) {
    let start = 0, end = nums.length - 1;
    let ans = nums.length; 
    
    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            start = mid + 1;
        } else {
            ans = mid; // 배열 내 target 값이 없는 경우 
            end = mid - 1;
        }
    }
    
    return ans;
};

 

이해에 참고한 글)

https://leetcode.com/problems/search-insert-position/solutions/3512849/c-java-python-javascript-o-logn-binary-search-with-explanation/