[Leetcode/파이썬] 35. Search Insert Position

Search Insert Position

---

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

 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        if nums[right] < target :
            return len(nums)

        while left < right :
            mid = (left + right) // 2
            if nums[mid] == target :
                return mid
            elif nums[mid] > target :
                right = mid
            else :
                left = mid + 1

        return left

문제의 마지막 문장을 보면 "O(log N)으로 해결하시오." 라고 가장 강력한 힌트를 주고 있다. 1/2 씩 줄여나가는 풀이법을 생각하면 된다. 대표적인 이분탐색을 활용하였다. 

여기서 중요한 점은 만약 target 이 작을때는 문제가 되지 않지만, max(nums)값을 초과하면 새로운 수를 추가해 줘야 한다. 그래서 코드 중간에 if 문을 하나 넣어 바로 반환하게 설계하였다. 

이후 아래 과정은 일반적인 이분탐색과 유사하니 참고하면 될 것이다.