[Leetcode] Search Insert Position

문제 출처

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

Search Insert Position - LeetCode

 

문제 해설

• 오름차순으로 정렬된 리스트(nums)에 순서를 유지하면서 정수(target)가 들어갈 수 있는 위치를 찾는 문제
• 시간 복잡도는 O(log n)가 되도록 코드를 구성

 

문제 풀이

# source: https://leetcode.com/problems/search-insert-position/?envType=study-plan&id=binary-search-i


class Solution:
    def searchInsert(self, nums: list, target: int) -> int:
        start = 0
        end = len(nums) - 1

        while start <= end:
            mid = (end + start) // 2

            point = nums[mid]
            if point == target:
                return mid
            if point > target:
                end = mid - 1
            elif point < target:
                start = mid + 1

        return start

• 삽입할 위치를  탐색하는데 시간복잡도가 O(log n)이 되어야하고 nums가 오름차순으로 정렬되어 제공되기 때문에 이진 탐색으로 접근
• 기존 이진 탐색과는 다르게 마지막까지 탐색해서 target이 삽입할 인덱스를 구해야하므로 함수 마지막에 start를 반환하는 로직을 추가하였다.

 

Github

• https://github.com/limseunghyun95/Algorithm_study/blob/master/leetcode/search_insert_position.py