刀模 东莞网站建设,专业做包装设计网站,网站与app的区别,网络运营商远端无响应怎么解决版本说明
当前版本号[20230928]。
版本修改说明20230928初版
35.搜索插入位置
点击此处跳转到力扣页面
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必…版本说明
当前版本号[20230928]。
版本修改说明20230928初版
35.搜索插入位置
点击此处跳转到力扣页面
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
思路
可以点击此篇博客看二分查找算法相关的图解究竟是什么样的讲解二分查找算法的博客让我写了三小时
这道题目是一个经典的二分查找问题要求在一个排序数组中找到目标值的索引如果目标值不存在则返回它将被按顺序插入的位置。
解题思路如下 首先定义两个指针 i 和 j分别指向数组的首部和尾部。 通过 while 循环不断缩小搜索的范围直到 i 大于 j。 在循环中计算中间位置 m (i j) 1无符号右移一位等价于除以2。 如果目标值小于等于中间值 nums[m]则说明目标值可能在左半部分将 j 更新为 m - 1。 如果目标值大于中间值 nums[m]则说明目标值可能在右半部分将 i 更新为 m 1。 重复上述步骤直到找到目标值或者搜索范围缩小到 i 大于 j找到目标值。 返回 i 的值即为目标值的索引或者插入位置。 该算法的时间复杂度为 O(log n)因为每次都将搜索范围缩小为原来的一半直到找到目标值或搜索范围为空。
代码
基础版
基础版代码具体的工作流程如下
首先定义两个指针 i 和 j分别指向数组的首部和尾部。通过 while 循环在满足 i j 的条件下进行查找。在循环中计算中间位置 m使用无符号右移一位 (i j) 1 来避免溢出。如果目标值 target 小于当前中间值 a[m]则说明目标值可能在左半部分将 j 更新为 m - 1。如果中间值 a[m] 小于目标值 target则说明目标值可能在右半部分将 i 更新为 m 1。如果中间值 a[m] 等于目标值 target则说明找到了目标值直接返回索引 m。重复上述步骤直到找到目标值或搜索范围缩小到 i j。最后如果找到了目标值则返回对应的索引如果没有找到则返回插入位置 i。
注原始代码中返回的是 -1但实际应该是返回插入位置 i。
public int searchInsert(int[] a, int target) {int i 0, j a.length - 1;while (i j) {int m (i j) 1;if (target a[m]) {j m - 1;} else if (a[m] target) {i m 1;} else {return m;}}return i; // 原始 return -1
}优化版
普通版与优化版这两段代码实际上是相同的只是变量名不同。
优化之处在于代码的可读性和简洁性通过使用有意义的变量名和清晰的逻辑结构使得代码更易于理解。返回值即为插入位置并能处理元素重复的情况。
将 target a[m] 与 target a[m] 的情况优化在一起target nums[m] 并少了一层的判断这样的优化并不会改变算法的时间复杂度和核心思想但可以提高代码的可读性和可维护性。
都是使用二分查找在给定的排序数组中找到目标值的索引如果目标值不存在则返回它将被按顺序插入的位置。
class Solution {public int searchInsert(int[] nums, int target) {int i 0;int j nums.length - 1;while (i j){int m (i j) 1;if(target nums[m]){j m -1 ;}else{i m 1 ;}}return i;}
}总结
这道题目是要求在给定的排序数组中使用二分查找的算法找到目标值的索引如果目标值不存在则返回它将被插入的位置。
总结一下解题思路和步骤 定义两个指针 i 和 j分别指向数组的首部和尾部。 使用 while 循环在满足 i j 的条件下进行查找。 在循环中通过计算中间位置 m 来获取中间元素的索引使用无符号右移一位 (i j) 1 来避免溢出。 如果目标值 target 小于当前中间值 a[m]则更新 j m - 1因为目标值可能在左半部分。 如果中间值 a[m] 小于目标值 target则更新 i m 1因为目标值可能在右半部分。 如果中间值 a[m] 等于目标值 target则说明找到了目标值直接返回索引 m。 重复上述步骤直到找到目标值或者搜索范围缩小到 i j。 最后如果找到了目标值则返回其索引如果没有找到则返回插入位置 i。 这种二分查找算法的时间复杂度为 O(log n)其中 n 是数组的长度。通过在每一次比较中将搜索范围缩小一半可以高效地找到目标值或插入位置。 在编码实现时需要注意边界条件、循环终止条件和变量更新的逻辑。通过理解并正确实现这个二分查找算法可以在排序数组中快速地找到目标值的索引或插入位置。
