今天的题目,利用的是二分查找原理。很不幸我又没做出来,但是也很高兴发现自己的不足~
一、题目
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
示例 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
二、思路解析
由于官方答案我看不明白,因此找了另一种比较便于理解的做法。
二分查找相信各位都在 C 语言学过,只是忘得七七八八了。
这个解法首先要定义三个变量:left 、 right 、 mid .
并分别赋值为 left = 0; right = nums.length-1 ;
mid 的定义先卖个关子,放到后面再说。
这点搞定之后,接下来只要理解概念,剩下的就很简单了。
分三种情况,nums[mid] == target 、 nums[mid] <= target 和 nums[mid] >mid ;
第一种情况,证明我们找到了,直接返回 mid 就行了,因为此时 mid 正好是插入元素的下标
第二种情况,则说明 mid 给的值还太小了,我们让 left ++,稍后再做解释
第三种跟第二种大差不差,mid 过大,我们先让 right --。
完成之后,我们再把这个过程循环一遍,同时,在 循环中定义变量 mid = ( right + left ) /2 ;
即可大功告成。文章来源:https://www.toymoban.com/news/detail-696559.html
三、完整代码
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target) {
return mid;
}
else if(nums[mid]<=target){
left = mid+1;
}
else {
right = mid-1;
}
}
return left;
}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!文章来源地址https://www.toymoban.com/news/detail-696559.html
到了这里,关于【力扣每日一题04】数组篇--搜索插入位置的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!