[leetCode][알고리즘] 35. Search Insert Position

문제 설명

LeetCode
35. Search Insert Position

찾는 대상이 있다면 해당 index를 리턴하고, 없다면 순서 상 들어갈 곳의 index를 리턴하세요.

알고리즘 복잡도는 O(log n)이어야 합니다. 

제한사항

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

입출력 예

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Input: nums = [1,3,5,6], target = 7
Output: 4

문제 풀이

이진탐색으로 찾으면 된다. (BinarySearch)

단, 예외처리 및 빠른 처리를 위해 target이 제일 작고/큰 경우만 먼저 체크했다. 

응용해서 우리는 isBadVersion(version) 기준으로 체크하면 된다.

문제의 배열은 1부터 시작하나, 우리는 0부터 체크하는 것만 유의하자.

1. nums는 항상 정렬된 순서로 들어온다는 점을 활용하여 예외처리한다.
2. 이진탐색으로 순서상 들어갈 곳(자신보다 작은 값 중 제일 큰 값의 다음 위치)을 찾는다. 

Code

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

결과