LeetBook/数组和字符串/搜索插入位置

举报
陈沧夜 发表于 2022/04/29 22:46:36 2022/04/29
【摘要】 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6], 5 ...

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/array-and-string/cxqdh/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  1. mid的计算方式:mid=(low+high)/2建议改为mid=low+(high+low)/2, 因为如果二分的上界超过int型数据32bit的一半,接下来在查找靠后的位置时候,high+low可能会溢出。low+(high+low)/2可以较好规避这个问题
  2. low<high 条件判断问题:当low<=high,while循环结束时我们得到的是 low>high,此时我们可以判定target存不存在。当low<high时,while循环结束时,low==high,得出的是当target存在时,target在数组中的位置
  3. 查找区间:区间应该尽可能覆盖所有的结果,如果查询的元素可能比数组中所有元素都大,那么上界为n,本题当目标值不存在时,得到的应该在的位置可能是n,故n应该也要包含进去
  4. 本题实际上查找的应该是第一个大于等于这个目标值的位置,当存在时是等于目标值的位置,当不存在时是第一个大于这个目标值的位置,即应该插入的位置
  5. 当目标值大于nums[mid]时,目标值应该在右半部分,大于等于这个目标值的区间应该是[mid+1,high]
  6. 当目标值小于nums[mid]时,目标值在左半部分,这时候要注意,大于等于这个目标值的数也可能是mid,所以区间应该是[low,mid]

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int low = 0 ;
        int high = nums.size(); //之所以不是nums.size()-1是因为当目标数不存在时,其位置可能在n上
        int mid = 0;
        while(low<high){
            mid = low+(high-low)/2;
            if(nums[mid]<target)
                low = mid + 1; 
            else
               high = mid;   }
            return low;
         }
    
};

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

文章来源: blog.csdn.net,作者:沧夜2021,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/CANGYE0504/article/details/112060812

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200