难度: Easy
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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 <= nums.length <= 104-104 <= nums[i] <= 104nums 为 无重复元素 的 升序 排列数组-104 <= target <= 104运行时间: 32 ms
内存: 15.4 MB
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
这个题解使用了二分查找的思路。首先定义左右边界 l 和 r，分别指向数组的开始和结束位置。然后使用 while 循环进行二分查找，每次循环都计算中点 mid，比较 nums[mid] 和 target 的大小关系。如果 nums[mid] >= target，说明目标值可能在左半部分，将右边界 r 移动到 mid；否则目标值在右半部分，将左边界 l 移动到 mid + 1。最终左右边界重合时，l 即为目标值应该插入的位置。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0 # 左边界指针
r = len(nums) # 右边界指针
while l < r:
mid = l + (r - l) // 2 # 计算中点位置
if nums[mid] >= target: # 如果中点值大于等于目标值
r = mid # 将右边界移动到中点
else: # 否则
l = mid + 1 # 将左边界移动到中点右侧
return l # 返回目标值应该插入的位置
在二分查找中，将r移动到mid而不是mid-1是为了确保不错过目标值target。如果nums[mid]等于target，那么mid就是一个可能的插入位置。将r设为mid而不是mid-1，可以保持搜索范围内仍包含当前找到的target的位置，从而确保能找到最左边的插入点。如果将r设为mid-1，则可能会错过正确的插入位置，尤其是当数组中存在多个相同的元素时。这种选择在效率上可能会导致额外的几次迭代，但在结果上更能确保正确性。
使用l < r作为循环条件的主要原因是避免在搜索空间为空时还执行循环体。在l等于r时，搜索空间为空，因此没有必要再继续检查。这样设计可以防止无限循环和访问数组越界。同时，因为算法在每次迭代时都精确调整l或r，所以当l等于r时，l指向的位置就是target应该插入的位置，从而确保不会错过目标值。
二分查找算法计算中点位置时使用的是mid = l + (r - l) / 2公式，这种方式可以防止在计算mid时可能发生的整数溢出（如果直接使用(l + r) / 2可能会溢出）。因此，即使数组中的元素值非常大或接近整型的极限值，只要不超过整型的表示范围，这种计算方法仍然有效，不会影响算法的正确性。
在二分查找中，每次迭代都是在缩小搜索范围，直到l与r重合。此时，l（或r）指向的位置正是target可以插入的正确位置。这是因为每次循环都是根据nums[mid]与target的比较来调整l或r，确保不会错过target应该存在的位置。当l与r重合时，这个位置就是最终确定的插入位置，无论target是否存在于数组中。