网站开发的背景知识与相关技术,android sdk,广州专业网站改版哪家好,dw做网站如何让背景变得透明题目描述
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5
输出: 2
…题目描述
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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)其中 n 是数组的长度。所以可实现一个二分查找算法用于在排序数组中查找一个目标值并返回目标值的索引或者它应该被插入的位置。
代码
/*** param {number[]} nums* param {number} target* return {number}*/
var searchInsert function(nums, target) {let left 0, right nums.length - 1; // 闭区间 [left, right]while (left right) { // 区间不为空// 循环不变量// nums[left-1] target// nums[right1] targetconst mid Math.floor((left right) / 2);if (nums[mid] target) {left mid 1; // 范围缩小到 [mid1, right]} else {right mid - 1; // 范围缩小到 [left, mid-1]}}return left;
}代码分析 初始化两个指针 left 和 right分别指向数组的起始和结束位置形成一个闭区间 [left, right]。 进入一个 while 循环条件是 left 小于等于 right即区间不为空。 在循环内部计算中间位置 mid使用 Math.floor((left right) / 2) 来确保 mid 是一个整数。 比较 nums[mid] 和 target 的值 如果 nums[mid] 小于 target则说明 target 可能在 mid 的右侧因此更新 left 为 mid 1这样新的搜索区间就变成了 [mid 1, right]。如果 nums[mid] 大于或等于 target则说明 target 可能在 mid 的左侧或 mid 本身因此更新 right 为 mid - 1这样新的搜索区间就变成了 [left, mid - 1]。 当 while 循环结束时left 指针将指向 target 应该被插入的位置。如果 target 在数组中存在left 将指向 target 的索引如果 target 不存在left 将指向 target 应该被插入的位置以保持数组的排序。 最后函数返回 left 作为结果。
这个算法的关键在于每次迭代都会将搜索区间减半这是通过比较中间元素和目标值来实现的。如果目标值在数组中算法最终会找到它如果目标值不在数组中算法会找到目标值应该被插入的位置以保持数组的排序。 这里可以自行走一遍示例因为最后返回的是left而判断最后是因为right减少导致循环结束所以得到正确结果
