LeetCode Top Interview 150) Search Insert Position

Question

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.

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:

---

---

정수 리스트nums가 있고 시간복잡도를 O(log n)으로 해결하는 문제입니다.
사실 로그복잡도로 해결해야할 문제들은 분할로 해결이 가능하다는 정도는 거의 암기 수준으로 알고 있는게 맞다고 생각합니다(지수의 역연산이 로그니까요).
가장 기본적이고 대표적인 이분 탐색 문제입니다. 정확한 값을 찾는 것이 아닌 target이 들어갈 위치를 찾습니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if nums[-1] < target:
            return len(nums)

        l,r = 0,len(nums)-1

        while l+1 < r:
            m = (l+r)//2
            if nums[m] < target:
                l = m
            elif nums[m] > target:
                r = m
            else:
                return m
        
        return l if nums[l] >= target else r
            

• l,r : 이분 탐색에 사용할 왼쪽, 오른쪽의 인덱스입니다. 양 끝의 인덱스로 초기화합니다.
• 이후로는 이분 탐색을 시작합니다. 중간값이 target보다 크냐 작냐를 통해 l,r값을 둘의 중간값인 m으로 저장합니다.
  • 삽입할 위치를 찾기 때문에 해당 값이 정확하게 내부에 있다면 해당 인덱스를 반환합니다.
• 같은 값이 없다면 (l+r)//2 계산으로 인해 r의 값이 l보다 항상 1만큼 더 큽니다. 이를 while문조건에 사용합니다.
• l또는 r값이 답이므로 조건에 맞게 반환합니다. target이 nums[r]보다 크다는 예외는 처음에 처리했습니다.

---

기본적인 이분탐색 문제였고 반복문은 단순하게 작성하고 삽입 조건에 맞게 시작과 마지막에서 조건을 조금 덧붙였습니다.