# 35. Search Insert Position
#### Difficulty: Easy
link: https://leetcode.com/problems/search-insert-position/

### 1. Binary Search
#### $O(log\ n)$ runtime, $O(1)$ space

題目限制$O(log\ n)$複雜度，所以想到用binary search，套用binary search模板如下。

##### python

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

或著，使用bisect套件。

import bisect

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

###### tags: `leetcode`