35. Search Insert Position

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

Search Insert Position - LeetCode

 

sorted array에 주어진 하나의 숫자를 정확한 위치에 insert하는 문제

조건에 꼭 O(log N)으로 풀라고 되어있다.

 

정렬되어있고 찾는다?

binary search 아니겠는가

 

근데 binary search 조건이 값을 찾는 것이지만

이건 정렬이 깨지지 않는 위치를 찾는 것이라 컨셉은 같지만 약간의 차이는 있다.

 

python solution1. iteration

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

        left = 0
        right = len(nums) - 1
        
        while left <= right:

            mid = ( left + right ) // 2

            print(left, right, mid)

            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1

        return left

 

아마 인터뷰를 본다면 이게 가정 적절한 답이 아닐까?

 

python solution2. recursion:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        
        mid = len(nums) // 2 

        if len(nums) == 0:
            return 0

        if nums[mid] == target:
            return mid
        elif nums[mid] > target: # go left
            return self.searchInsert(nums[:mid], target)
        else: # go right
            res = self.searchInsert(nums[mid+1:], target)
            return mid + res + 1

        return None

 

recursion으로 작성하는게 좀 복잡한 문제지만 굳이 한다면 이렇게