Leetcode 35. 搜索插入位置

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 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

思路：
解法1：bisect_left函数
python有二分查找的轮子：bisect模块，该模块主要有两类重要函数：bisect和insort。

bisect：利用二分查找算法在有序序列中查找元素
bisect_left: 在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置
bisect_right(bisect): 在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置
insort：利用二分查找算法在有序序列中插入元素
insort_left: 将x插入到列表L中，x存在时插入在左侧
insort_right(insort): 将x插入到列表L中，x存在时插入在右侧

import bisect
L = [1,3,3,4,6,8,12,15]
x_sect_point = bisect.bisect_left(L, 3)  # 在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置
print(x_sect_point)  # 1
x_sect_point = bisect.bisect_left(L, 5)  # 在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置
print(x_sect_point)  # 4

x_sect_point = bisect.bisect_right(L, 3)  # 在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置
print(x_sect_point)  # 3
x_sect_point = bisect.bisect_right(L, 5)  # 在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置
print(x_sect_point)  # 4

bisect.insort_left(L, 2)  # 将x插入到列表L中，x存在时插入在左侧
print(L)  # [1, 2, 3, 3, 4, 6, 8, 12, 15]

bisect.insort_right(L, 4)  # 将x插入到列表L中，x存在时插入在右侧
print(L)  # [1, 2, 3, 3, 4, 4, 6, 8, 12, 15]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

python：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect_left(nums,target)
1
2
3

解法2：二分查找
相同的时候往左边找
python：

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