Search Insert Position

Search Insert Position

문제

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.

풀이

정렬된 배열에 target을 삽입하려 할 때 적절한 위치를 찾는 문제이다.

파이썬의 이진탐색 bisect 라이브러리에는 bisect_left, bisect_right등 다양한 메서드들을 제공한다.

• bisect_left(정렬된 리스트, target) return target을 삽입할 위치
• bisect_right(정렬된 리스트, target) return target을 삽입할 위치 + 1

이진탐색을 직접 구현해서 풀이할 수 있지만 이미 숙지하고 있으므로 라이브러리의 사용도 중요하다 생각해서 라이브러리를 사용했다.

Solution(Runtime: 36ms)

from bisect import bisect_left

class Solution(object):
    def searchInsert(self, nums, target):
        return bisect_left(nums, target)