LeetCode 35 (Easy) Search Insert Position

출처: leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

문제

한글 번역은 아래 더보기를 클릭해주세요.

유니크한 정수로 이루어진 배열과 임의의 값이 주어졌을 때,
임의의 값이 배열의 원소이면 해당 원소의 인덱스를 반환하고, 
임의의 값이 배열의 원소가 아니면, 임의의 값이 오름차순으로 추가되었을 때의 인덱스를 반환하라.

 

예제 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

예제 5:

• 입력: nums = [1], target = 0
• 출력: 0

제약조건:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums는 유니크한 값으로 이루어져 있으며, 오름차순으로 정렬되어 있다.
• -10^4 <= target <= 10^4

풀이

• 이진탐색으로 탐색
• 값을 찾으면 해당 인덱스를 리턴
• 값이 크면, 해당 인덱스를 저장하고, 왼쪽을 찾는다
• 값이 작으면, 해당 인덱스 + 1을 저장하고, 오른쪽을 찾는다

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1
        answer = -1
        
        while start <= end:
            mid = (start + end) // 2
            
            if nums[mid] == target:
                answer = mid
                break
            elif nums[mid] > target:
                answer = mid
                end = mid - 1
            else:
                answer = mid + 1
                start = mid + 1
        
        return answer

결과