问题描述
给定一个已排序的整数数组 nums 和一个目标值 target，要求在数组中找到目标值并返回其索引。如果目标值不存在于数组中，则返回它按顺序插入的位置。必须使用时间复杂度为 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
解题思路
为什么用二分查找？
由于数组已排序，且要求时间复杂度为 O(log n)，自然联想到二分查找。但不同于标准二分查找的是，当目标值不存在时，需要找到插入的位置。
核心思路
-
初始化指针：定义两个指针
left和right，分别指向数组的首尾。 -
二分缩小范围：
-
计算中间索引
mid。 -
比较
nums[mid]与target：-
若
nums[mid] < target，说明目标值在右半部分，调整left = mid + 1。 -
否则，调整
right = mid - 1，因为此时mid可能是插入点或目标值在左半部分。
-
-
-
终止条件：当
left > right时，循环结束。此时left即为目标值的插入位置（若不存在）或目标值的位置（若存在）。
为什么返回 left？
-
存在目标值：在循环中会不断调整指针，最终
mid命中目标值，循环结束时left即为目标值的位置。 -
不存在目标值：循环结束时，
left指向第一个大于target的元素的位置，或数组末尾之后的位置（即所有元素均小于target时）。
示例分析（示例2）：
-
nums = [1,3,5,6], target = 2 -
初始：
left=0,right=3→mid=1，nums[1]=3 > 2→right=0 -
下一轮：
left=0,right=0→mid=0，nums[0]=1 < 2→left=1 -
循环结束，返回
left=1（即插入位置）。
代码实现
class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2; // 防止溢出if (nums[mid] < target) {left = mid + 1; // 目标在右半部分} else {right = mid - 1; // 目标在左半部分或mid处}}return left; // left即为插入位置}
}复杂度分析
-
时间复杂度：
O(log n)。每次循环将搜索范围减半，最多执行log n次循环。 -
空间复杂度：
O(1)。仅使用常数级别的额外空间。
总结
通过二分查找的变体，我们巧妙地利用指针调整策略，最终返回 left 的值作为目标值的插入位置。该算法高效且简洁，完美满足了题目的所有要求。理解这一过程的关键在于明确循环结束时 left 指针的意义，即第一个大于等于目标值的位置。