[LeetCode] 35. Search Insert Position

문제링크

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

Search Insert Position - LeetCode

 

코드

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        if target>nums[right]:
            return right+1
        if target<nums[0]:
            return 0
        while left<=right:
            pivot = (left+right)//2
            cur = nums[pivot]
            prior = nums[pivot-1]
            if cur ==target or (target <cur and target>prior):
                return pivot
            elif cur>target:
                right = pivot-1
            else:
                left = pivot+1

 

 

POINT

-풀이방법:

Binary Search로 접근한다.

우선, target을 nums의 최소값[0], 최대값[-1]과 비교해본다.

그 다음 이진탐색을 적용하는데, pivot-1값보단 크고 pivot값보다 작은 경우도 발견해야하므로 이진탐색 종료 조건에 이 경우를 추가하였다. 

-Complexity Analysis:

1) Time Complexity : O(logN)

2) Space Complexity: O(1)