原题地址：. - 力扣（LeetCode）
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
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提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
解题思路
- 初始化：如果数组为空或
null，返回 -1，表示无法查找。否则，初始化start为 0，end为数组长度减一。- 二分查找：在
start + 1 < end的条件下进行循环。取中间索引midd = start + (end - start) / 2：
- 如果
nums[midd] == target，则返回midd。- 如果
nums[midd] > target，说明target在左半部分，因此将end更新为midd。- 否则，将
start更新为midd。- 边界检查：循环结束后，检查
start和end指针位置是否为target，如果是，则返回对应索引。- 确定插入位置：如果没有找到
target，则检查target应插入的位置。若target小于nums[end]，则插入位置在start或start + 1处；否则，在end + 1处
源码实现
java">class Solution {public int searchInsert(int[] nums, int target) {// 检查数组是否为空if (null == nums || nums.length == 0) {return -1; // 若为空数组，返回 -1 表示无效输入}int start = 0; // 左指针int end = nums.length - 1; // 右指针int midd; // 中间指针// 二分查找，当 start 和 end 相邻时退出循环while (start + 1 < end) {// 防止 start + end 直接相加可能导致的整型溢出midd = start + (end - start) / 2;if (nums[midd] == target) {return midd; // 找到目标，返回其索引} else if (nums[midd] > target) {end = midd; // target 在左半部分，缩小右边界} else {start = midd; // target 在右半部分，缩小左边界}}// 边界检查，确保是否找到 targetif (nums[start] == target) {return start; // target 在 start 索引}if (nums[end] == target) {return end; // target 在 end 索引}// 判断 target 的插入位置if (target < nums[end]) {// target 应插入到 start 或 start + 1 的位置return nums[start] < target ? start + 1 : start;} else {// target 大于 end 位置元素，应插入到 end + 1return end + 1;}}
}
复杂度分析
- 时间复杂度：O(log n)，因为使用了二分查找，每次循环将查找范围减半。
- 空间复杂度：O(1)，仅使用了常数级别的额外空间（
start、end、midd变量）。
