[LeetCode] 35 | Search Insert Position

35 | Search Insert Position
https://leetcode.com/problems/search-insert-position/

 

 

 

 

작성 코드

 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for idx, value in enumerate(nums):
            if value >= target:
                return idx
        return len(nums)

 

• nums 를 돌면서 taget 값보다 value 값이 클 때가 삽입할 경우이므로 return
• 만약 for문을 돌아도 return이 안 됐다면 제일 마지막에 삽입해야하는 경우이므로 len(nums) return

 

 

이상 코드

 

이진 탐색 구현

 

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

 

• low < high 경우에만 반복문 진행
• mid 값을 구하여 taregt 값보다 nums[mid]가 크다면 low 값을 mid + 1로 갱신, 아니라면 high = mid로 갱신

 

 

 

이진 탐색 - python 라이브러리 이용

 

 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

 

• bisect_left 함수를 이용하여 첫번째 인자 값으로 배열, 두번째 인자 값으로 target 값 넘겨줌