响应式设计 手机网站,一键搭建论坛,网络工程师主要做什么,wordpress怎么修改登录界面问题描述
给定一个已排序的整数数组 nums 和一个目标值 target#xff0c;要求在数组中找到目标值并返回其索引。如果目标值不存在于数组中#xff0c;则返回它按顺序插入的位置。必须使用时间复杂度为 O(log n) 的算法。
示例#xff1a; 示例1#xff1a; 输入: nums …问题描述
给定一个已排序的整数数组 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 初始left0, right3 → mid1nums[1]3 2 → right0 下一轮left0, right0 → mid0nums[0]1 2 → left1 循环结束返回 left1即插入位置。
代码实现
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 指针的意义即第一个大于等于目标值的位置。
