Search Insert Position

문제설명

정렬된 중복되지 않는 정수 배열과 목표 값을 고려할 때, 목표 값이 배열에서 발견되면 해당 인덱스를 반환합니다. 발견되지 않으면, 정렬된 순서대로 삽입될 수 있는 인덱스를 반환합니다.

알고리즘은 (O(log n)) 시간 복잡도로 작성되어야 합니다.

예제 1:

입력: nums = [1,3,5,6], target = 5
출력: 2

예제 2:

입력: nums = [1,3,5,6], target = 2
출력: 1

예제 3:

입력: nums = [1,3,5,6], target = 7
출력: 4

문제풀이

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

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

<내 코드의 흐름>

1. searchInsert라는 메소드를 정의합니다.

• 이 메소드는 nums라는 정수 리스트와 target이라는 정수를 인자로 받아, 정수를 반환합니다.
• nums 리스트는 정렬된 상태로 주어집니다.

2. 두 개의 포인터 left와 right를 초기화합니다.

• left는 리스트의 시작을 가리키고, right는 리스트의 끝을 가리킵니다.

3. left가 right보다 작거나 같은 동안 반복문을 실행합니다.

• 이 반복문은 이진 탐색을 수행합니다.

4. mid는 left와 right의 중간 인덱스를 계산합니다.

• // 연산자는 나눗셈의 결과를 정수로 반환합니다.

5. nums 리스트의 중간 값이 target과 같다면, mid 인덱스를 반환합니다.

• target이 리스트에 존재하는 경우입니다.

6. nums[mid]가 target보다 작다면, left 포인터를 mid + 1로 이동시킵니다.

• target이 리스트의 오른쪽 부분에 있을 때 수행됩니다.

7. nums[mid]가 target보다 크다면, right 포인터를 mid - 1로 이동시킵니다.

• target이 리스트의 왼쪽 부분에 있을 때 수행됩니다.

8. while 루프가 종료된 후, left 포인터는 target이 삽입되어야 할 위치를 가리킵니다. 따라서 left를 반환합니다.