35. Search Insert Position

35. Search Insert Position

 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # O(log n) 이므로, 이진 탐색 BST 사용
        l, r= 0, len(nums)-1
        while(l<r):
            mid = (r+l)//2
            if nums[mid] < target:
                l = mid+1
            elif nums[mid] > target:
                r = mid-1
            else:
                return mid

        # 못찾으면, 
        # target > nums[l] 이면, 
        #  target을 l+1에 값을 넣어야 하니, l+1을 반환
        # 아니면, target < nums[l] 이니,
        #  target을 l에 값을 넣고, 나머지는 오른쪽으로 하나씩 밀어야 하니
        #  l을 반환            
        return l+1 if target > nums[l] else l

 

while (l < r)와 while (l <= r)의 차이점:

• while (l < r)
  • 마지막 값은 탐색하지 않고 종료하므로, 종료 후 값 비교가 필요합니다.
• while (l <= r)
  • 모든 값을 탐색하지만, 루프 종료 후 삽입 위치는 항상 l 입니다

 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # O(log n) 이므로, 이진 탐색 BST 사용
        l, r= 0, len(nums)-1
        while(l<=r):
            mid = (r+l)//2
            if nums[mid] < target:
                l = mid+1
            elif nums[mid] > target:
                r = mid-1
            else:
                return mid

        # 못찾으면, 
        return l