leetCode) 35. Search Insert Position

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

Search Insert Position - LeetCode

나의 풀이)

시간 복잡도를 생각하지 않고 푼 코드는 다음과 같다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let index = 0;
    
    while (true) {
        if (nums[index] < target) {
            if (index === nums.length - 1) {
                return nums.length;
                continue;
            }
            
            index += 1;
            continue;
        }
        
        return index;
    }
};

시간 복잡도를 고려하여 알고리즘을 풀어본 경험이 거의 없었다는 것을 알게 되었고,

검색 결과 이진 탐색으로 풀어내신 분의 글을 읽게 되었다.

 

그래서 나도 이진 탐색으로 풀어보았다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if (target <= nums[0]) {
        return 0;
    }
    
    let start = 0;
    let end = nums.length - 1;
    let mid = null;
    
    while (start <= end) {
        mid = Math.floor((start + end) / 2);
        
        if (nums[mid] === target) {
            return mid;
        }
        
        if (nums[mid] > target) {
            end = mid - 1;
            continue;
        }
        
        start = mid + 1;
    }
    
    return start;
};

제대로 풀었다는 느낌이 들었고, 이진 탐색 알고리즘을 실제로 적용해보았던 점이 보람찼던 것 같다.