LeetCode 35. 搜索插入位置：二分查找的边界条件深度解析

摘要
本文详细解析 LeetCode 35 题《搜索插入位置》的解题思路，重点探讨二分查找中循环条件 left <= right 的必要性，并提供 Java 实现代码。通过边界案例分析和常见错误解答，帮助读者深入理解二分查找的边界处理逻辑。

---

问题描述

给定一个升序排列的整数数组 nums 和一个目标值 target，要求找到 target 在数组中的插入位置。若 target 已存在于数组中，则返回其索引；否则返回其按升序插入的位置。
示例：

• 输入：nums = [1,3,5,6], target = 5 → 输出：2
• 输入：nums = [1,3,5,6], target = 2 → 输出：1

---

方法思路：二分查找

二分查找是解决有序数组搜索问题的经典算法，其核心是通过不断缩小搜索范围定位目标值。以下是具体步骤：

1. 初始化指针

• left：指向数组起始位置（0）。
• right：指向数组末尾位置（nums.length - 1）。

2. 循环条件与中间值计算

• 循环条件：使用 left <= right 确保所有元素都被检查。
• 中间值计算：mid = left + (right - left) / 2（避免整数溢出）。

3. 调整指针范围

• 若 nums[mid] == target：直接返回 mid。
• 若 nums[mid] < target：说明目标值在右半部分，调整 left = mid + 1。
• 若 nums[mid] > target：说明目标值在左半部分，调整 right = mid - 1。

4. 确定插入位置

循环结束时，left 指向第一个大于 target 的元素位置，或数组末尾（即插入位置）。

---

解决代码

class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {  // 必须用 <= 保证所有元素被检查int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;  // left 是第一个大于 target 的位置}
}

---

代码解释

代码片段	说明
int left = 0, right = nums.length - 1	初始化指针，覆盖整个数组范围。
while (left <= right)	关键点：保证所有元素被检查，尤其是 left == right 的情况。
mid = left + (right - left) / 2	防止 (left + right) 导致的整数溢出。
if (nums[mid] == target)	找到目标值，直接返回索引。
left = mid + 1 / right = mid - 1	缩小搜索范围，逐步逼近目标位置。
return left	循环结束时，left 指向插入位置。

---

常见问题

1. 为什么循环条件必须是 left <= right，用 left < right 会报错？

• 错误示例：数组 [5]，目标值 7。

  • 若使用 left < right，循环不会执行，直接返回 left = 0（错误）。
  • 正确插入位置应为 1。

• 根本原因：
  left < right 在 left == right 时跳过循环，导致最后一个元素未被检查。此时：

  • 若目标值等于最后一个元素，无法返回正确索引。
  • 若目标值大于最后一个元素，错误返回 left 而非 left + 1。

2. 如何处理重复元素？

• 若存在多个 target，返回第一个匹配的索引（因升序数组的特性，二分查找天然优先定位到左侧）。

3. 时间复杂度与空间复杂度

• 时间复杂度：O(log n)，二分查找每次缩小一半搜索范围。
• 空间复杂度：O(1)，仅使用常数级别额外空间。

---

总结

• 核心技巧：正确使用 left <= right 循环条件，确保所有边界情况被覆盖。
• 适用场景：有序数组的搜索、插入位置问题（如 LeetCode 34、278、704 题）。
• 扩展思考：若数组为降序排列，如何调整比较逻辑？

题目链接：LeetCode 35. 搜索插入位置