题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1：
输入: nums = [1,3,5,6], target = 5
输出: 2提示
一句话思路：标准二分查找，找「第一个 >= target 的位置」（lower_bound）。
left和right缩小区间：nums[mid] < target说明目标在右半边，left = mid + 1；否则在左半边，right = mid - 1。- 循环结束时
left就是插入位置：target存在：left指向它的索引；target不存在：left指向第一个比它大的元素位置，即应有的插入点。
- 注意循环条件是
left <= right，不是<，否则区间只有一个元素时会漏掉。 - 时间 O(log n)、空间 O(1)。
答案
python
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
def lower_bound(nums: List[int], target: int) -> int: # 二分查找：找第一个 >= target 的位置
left = 0
right = len(nums) - 1
while left <= right: # 区间不为空就继续
mid = (left + right) // 2
if nums[mid] < target: # 目标在右半边，左边界右移
left = mid + 1
else: # 目标在左半边（含 mid），右边界左移
right = mid - 1
return left # left 即为第一个 >= target 的位置
return lower_bound(nums, target)
留言板