[LeetCode] 35. Search Insert Position (Python3)

Description

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

풀이

O(log n)에 맞춰 풀어야 하는 문제로, 배열이 정렬됐기 때문에 binary search를 이용하면 쉽게 풀리는 문제이다.

타겟값이 없을 경우 들어가기 가장 적합한 곳의 인덱스를 반환해야 하는데, left와 right을 이리저리 옮겨다니면 최종적으로 멈추는 그 자리가 바로 적합한 자리이다.

최종적으로 현재 숫자들이 오른차순으로 되어있기 때문에 left를 반환시키면 된다.

코드

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            pivot = (left + right) // 2

            if nums[pivot] == target:
                return pivot
            elif nums[pivot] < target:
                left = pivot + 1
            else:
                right = pivot - 1
        return left