LeetCode 35 - Search Insert Position (Easy)

 

💡 문제

LeetCode -35번

 

🎯 풀이 과정

target 이 배열에 존재할 경우 해당 요소의 index를, 만약 존재하지 않을 경우

target 이 위치해야할 index 를 반환하는 함수를 구현하는 문제입니다.

문제 조건에서 따라 정렬된 배열에서 이분 탐색 을 사용하면 O(logn) 에 해결할 수 있습니다.

 

👨‍💻 코드

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

    function findItem(head, tail) {
        if (head >= tail) {
            if (nums[head] === target) {
                answer = head
            } else {
                answer = nums[head] > target ? head : head + 1
            }

            return
        }

        const mid = head + Math.floor((tail - head) / 2)

        if (nums[mid] === target) {
            answer = mid
        } else if (nums[mid] < target) {
            findItem(mid + 1, tail)
        } else {
            findItem(head, mid - 1)
        }
    }

    findItem(0, nums.length - 1)

    return answer
};