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

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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