Search Insert Position

•

문제 링크 : https://leetcode.com/problems/search-insert-position/description/

•

문제 설명 : Array와 target 값을 제공한다. target 값이 존재하는 index를 찾거나, target이 Array에 설정되면 어느 인덱스에 설정되어야하는지 구한다.

•

풀이 방법

◦

O(logN) 방식의 풀이를 보고, 이진 탐색 트리를 떠올려 사용하였다.

•

성공 코드

def searchInsert(self, nums: List[int], target: int) -> int:
    start = 0
    end = len(nums) - 1 # O(1)

    # 이진 탐색 방식 사용 O(log2N)
    # start 혹은 end를 조절하여, 매 탐색 범위가 절반씩 줄어듦
    while start <= end:
        temp = (start + end) // 2

        if target > nums[temp]:
            start = temp + 1
        else:
            end = temp - 1

    # target이 설정되어야하는 Index를 구해야하기 때문에, start를 반환한다.
    # 마지막에 start를 +1 하면서, start가 end보다 커지며 종료되는 구조이기 때문이다.
    return start
Python
복사