[Leetcode] 35. Search Insert Position

Problem:

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

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

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

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

Constraints:

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

 

Solution1:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        index = 0 
        for i in range(len(nums)):
            if nums[i] == target:
                return i 
            elif nums[i] < target:
                index += 1 
        return index

이 solution은 시간복잡도가 O(n)이다. 물론 accept 되긴 하지만, 완전탐색이기 때문에, 더 나은 방향을 찾아봐야 한다. 

 

Solution2:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l,r = 0, len(nums) - 1 
        mid = 0 
        while l <= r:
            mid = (l + r) // 2 
            if target == nums[mid]:
                return mid 
            elif nums[mid] < target:
                l = mid + 1 
            else:
                r = mid -1 
        return l

이 solution은 시간복잡도가 O(log(n))이다. Binary Search를 이용하여 문제를 풀었다. 나는 이 발상이 떠오르지 않았다. 물론 Binary Search는 떠올랐지만, 어떻게 insertion을 진행할까? 에 대하여 너무 복잡하게 생각했다. 실상은 마지막까지 찾다가 못 찾으면 그냥 집어넣으면 되는 거였다. 내가 이걸 생각하지 못한 이유는 Binary Search에서 mid값을 찾을 때 이 mid값의 뜻을 완전히 이해하지 못해서였다. mid는 단지 중앙값이 아닌 내가 찾고자 하는 값으로 가는 값이었던 것이다.