📃 문제 설명

Search Insert Position

[문제 출처 : LeetCode]

👨‍💻 해결 방법

주어진 수가 리스트에 있으면 인덱스를 반환하고,
없으면 오름차순 정렬 기준, 삽입되어야할 올바른 인덱스를 찾아서 반환하면 된다.

처음에는 단순하게 생각해서 풀었는데,
이진 탐색을 이용하면 좀 더 시간복잡도를 줄일 수 있을 것 같았다.

그래서 이진 탐색을 사용하여 다시 풀었다.
재밌다.

이진 탐색

👨‍💻 소스 코드

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

        while left <= right:
            middle = (left + right) >> 1
            if nums[middle] == target:
                return middle
            if target < nums[middle]:
                right = middle - 1
            else:
                left = middle + 1
        return left