[Leetcode] 35. Search Insert Position

Problem

문제 링크

주어진 배열에서 타겟으로 주어진 숫자값을 찾는 문제.
이때 타겟값이 없다면 타겟값을 삽입했을때 와야할 인덱스를 반납한다.

Solution

O(logn) 으로 풀기위해서 이진탐색을 이용함.

이진탐색을 이용하여 문제를 해결한다.
이때 조건을 왼쪽 인덱스는 target보다 작게 조건을 정의하고 오른쪽 인덱스를 target을 포함한 높은 값으로 조건을 잡아주면 해당 문제를 해결할 수 있다.

오른쪽 값은 타겟이 있을경우 타겟값을 아닐경우 타겟이 올 수 있는 인덱스를 반납하게된다. (타겟과 가장 근접한 큰 수의 위치이기 때문에)

JS Code

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