算法21，搜索插入位置
一道经典的二分查找应用题，通常被称为“搜索插入位置”。笔记中的思路非常清晰，下面为你整理这道题的具体解法、代码实现以及需要注意的细节。
1. 题目理解
题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
核心要求：时间复杂度为 O(logN)，这意味着必须使用二分查找。
关键结论：这道题本质上是在寻找数组中第一个大于等于目标值（>= target）的元素位置。
2. 算法思路（基于笔记）
笔记中总结了寻找“左边界”的逻辑，这正是解决此题的核心：
初始化：左指针
left = 0，右指针right = nums.length - 1。循环条件：
while (left < right)。注意：这里不能写成
left <= right，因为当left == right时，我们已经找到了唯一的目标位置，应该退出循环直接返回。
中间值计算：
int mid = left + (right - left) / 2;（防止整数溢出）。比较与收缩：
如果
nums[mid] < target：说明目标值在右边，且肯定不是mid，所以left = mid + 1。如果
nums[mid] >= target：说明目标值在左边（或者是mid本身），我们需要继续向左寻找第一个满足条件的位置，所以right = mid。
返回结果：循环结束时，
left和right指向同一个位置，这个位置就是我们要找的插入点。直接返回left即可。
3. 代码实现（Java）
public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 循环条件：left < right while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 目标在右侧，且 mid 已经排除 left = mid + 1; } else { // 目标在左侧或等于 mid，保留 mid，收缩右边界 // 这里的 else 涵盖了 nums[mid] >= target 的情况 right = mid; } } // 根据题意，数组为空时也应返回0，上述逻辑天然支持 return left; }4. 细节辨析（为什么返回left？）
笔记右下角有一个手写的补充说明：“if (nums[left] < target) return left + 1;”。
其实，在使用while (left < right)和right = mid这种模板时，循环结束后的left已经具有了“第一个大于等于 target 的位置”的性质，不需要额外的 if 判断。
我们可以推演一下那个手写逻辑的场景：
场景 A：如果循环结束时，
nums[left] >= target。说明
left就是我们要插入的位置（或者是已经存在的目标）。此时直接返回
left。
场景 B：如果循环结束时，
nums[left] < target。这种情况只可能发生在
left指向了数组的最后一个元素之后（即left == nums.length）。为什么会这样？因为当
mid计算到最后几个元素时，如果它们都小于target，left会不断被推到mid + 1，直到越出数组边界。此时
left指向的位置确实是原数组长度，也就是正确的插入位置。(注：但在 Java 中，如果数组长度是 5，
right最大只能是 4，所以left最大也只能是 5。当left=5时，nums[left]会越界。因此，最安全的写法就是直接return left，无需先判断。)
总结：笔记中的代码逻辑是非常标准的“寻找左边界”模板，直接返回left即可完美解决该问题。