35. 搜索插入位置

分析

1. 定义搜索范围：
   • 使用两个指针 l 和 r 分别表示数组的左边界和右边界，初始值为 0 和 nums.size()
   • 注意右边界初始值为 nums.size()，因为我们需要处理目标值可能插入在数组末尾的情况
2. 进行二分查找：
   • 计算中间位置 mid = (l + r) >> 1
   • 如果 target <= nums[mid]：
     • target 可能在 mid 位置或其左侧，更新右边界 r = mid
   • 如果 target > nums[mid]：
     • target 一定在 mid 右侧，更新左边界 l = mid + 1
3. 返回结果：
   • 最终，l 和 r 会收敛到目标值的位置
   • 如果 target 不在数组中，返回的是它应该插入的位置

时间复杂度

二分查找的时间复杂度为 O(log n)，其中 n 是数组长度

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int searchInsert(vector<int>& nums, int target)
{
  int l = 0, r = nums.size();
  while (l < r)  // 当左边界小于右边界时，继续搜索
  {
    int mid = (l + r) >> 1;  // 计算中点
    if (target <= nums[mid])
      r = mid;  // 缩小右边界，可能找到目标或插入点
    else
      l = mid + 1;  // 缩小左边界
  }
  return r;  // 返回插入位置
}