LeetCode 35.Search Insert Position (Python)

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

Search Insert Position - LeetCode

Solution 1 

• 시간복잡도 : O(N)
• 공간복잡도 : O(1)

아이디어 (Brute- Force)

배열을 0에서부터 순회하고, target의 값과 같거나 크다면 순회 중단하고 중단한 시점의 인덱스를 반환한다. 

# 1. Brute force
def searchInsert(nums: List[int], target: int) -> int:
    index = 0

    while index < len(nums):
        if target <= nums[index]:
            break

        index += 1

    return index

Solution 2

• 시간복잡도 : O(logN)
• 공간복잡도 : O(1)

아이디어(Hash Table)

해쉬(딕셔너리) 를 사용하는데 이진탐색으로 탐색 속도를 높인다. 

이진탐색을 접한 횟수가 많다보니 대하는 느낌이 확실히 편해졌다. 

 

def searchInsert(nums: List[int], target: int) -> int:
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = int((low+high) / 2)

        if target == nums[mid]:
            return mid
        if target > nums[mid]:
            low = mid + 1
        else:
            high = mid -1

    return low