99클럽 코테 스터디 12일차 35. Search Insert Position

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

 

정수들이 오름차순으로 정렬된 배열과 타겟 값을 입력으로 받아, 타겟이 발견되면 그 인덱스를 반환하세요. 만약 타겟이 발견되지 않으면, 타겟이 정렬된 순서에 삽입될 위치의 인덱스를 반환하세요. 알고리즘은 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

예제 4:

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

제약 조건:

• 배열 nums의 길이는 1 이상 10,000 이하입니다.
• nums[i]의 값은 -10,000 이상 10,000 이하입니다.
• 배열 nums는 중복되지 않는 값들로 이루어져 있으며, 오름차순으로 정렬되어 있습니다.
• 타겟 target의 값은 -10,000 이상 10,000 이하입니다.

 

 

 

풀이

이진탐색을 이용한다.

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

이진 탐색의 거의 정석인 코드

 

• left와 right는 배열의 처음과 끝을 나타내는 인덱스
• while left <= right 조건으로 탐색 범위를 계속 줄임
• mid는 현재 탐색 범위의 중간 위치를 계산한 값
• nums[mid]와 target을 비교하여 다음과 같은 경우를 처리
  • 타겟 값이 중간 값과 같으면, 해당 위치의 인덱스를 반환
  • 타겟 값이 중간 값보다 크면, 탐색 범위를 오른쪽으로 좁힌다 (left = mid + 1).
  • 타겟 값이 중간 값보다 작으면, 탐색 범위를 왼쪽으로 좁힌다 (right = mid - 1).
• 타겟 값이 배열에 없을 경우, left는 타겟 값이 들어갈 위치를 가리키게 되므로 이를 반환