搜索插入位置

题目描述#

方案一：线性扫描（初步尝试）#

核心思路： 遍历数组，找到第一个大于或等于 target 的元素下标。如果遍历完都没找到，说明 target 应该插在数组末尾。

1
class Solution {
2
public:
3
    int searchInsert(vector<int>& nums, int target) {
4
        for (int i = 0; i < nums.size(); ++i) {
5
            if (nums[i] >= target) {
6
                return i;
7
            }
8
        }
9
        return nums.size();
10
    }
11
};

方案二：二分查找（进阶解法）#

核心思路： 利用数组已排序的特性，采用“折半查找”的思想。通过不断缩小目标值所在的区间，将搜索时间从线性降低到对数级别。

1
class Solution {
2
public:
3
    int searchInsert(vector<int>& nums, int target) {
4
        int left = 0, right = nums.size(); // 定义 [left, right)
5

6
        while (left < right) {             // 当闭区间不为空
7
            int mid = left + (right - left) / 2; // 防止溢出的中点写法
8

9
            if (nums[mid] < target) {
10
                left = mid + 1;            // 目标在右侧，缩小左边界
11
            } else {
12
                right = mid;               // 目标在左侧或就是 mid，缩小右边界
13
            }
14
        }
15
        return left; // 最终 left == right，即为插入位置
16
    }
17
};

深度解析：为什么 right = nums.size()？#

在二分查找中，边界处理（Boundary Conditions）是公认的难点。

• 左闭右开 [left, right)：初值设为 right = nums.size()。
  • 循环条件是 while (left < right)。
  • 当 target 大于数组所有元素时，left 会一直增加直到等于 nums.size()，最终返回的值正好是末尾插入位置。
• 防止溢出：使用 left + (right - left) / 2 而非 (left + right) / 2，是为了在大数运算时防止 left + right 导致整型溢出。

总结#

• 有序即二分：看到“有序数组”和“查找”这两个关键词，第一时间要联想到二分查找。
• 复杂度达标：题目明确要求 $O(\log n)$，因此线性扫描虽然能通过（在数据量小时），但在面试中不符合要求。