目录

原题：搜索插入位置

题目描述

 解题思路

 代码执行

复杂度分析

结语 

【前言】：HelloHello大家好，又见面喽，今天是力扣打卡第5天！还有没有小伙伴没有上车呢，记得每天坚持刷题哦。

原题：搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

【敲黑板】：遇到这种搜索题时间复杂度要求是O(logN)的，记得采用二分法哦

示例1：

  

   

    

     

    
    

     

      输入: nums = [1,3,5,6], target = 5
     
    
   

    

     

    
    

     

      输出: 2
     
    
  
 

 示例2：

  

   

    

     

    
    

     

      输入: nums = [1,3,5,6], target = 2
     
    
   

    

     

    
    

     

      输出: 1
     
    
  
 

 解题思路

对于这题，由于是在已经排好序的数组中查找元素，而且要求时间复杂度是O(logN)，所以我们很容易就想起来利用二分法解题。

 代码执行

  

   

    

     

    
    

     

      int searchInsert(int* nums, int numsSize, int target){
     
    
   

    

     

    
    

     
    if(nums == NULL || numsSize == 0){
     
    
   

    

     

    
    

     
        return -1;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    int left = 0;
     
    
   

    

     

    
    

     
    int right = numsSize - 1;
     
    
   

    

     

    
    

     
    int mid = 0;
     
    
   

    

     

    
    

     
    //注意为什么不是left <= right ,因为当left == right时就不知道要插哪里去了
     
    
   

    

     

    
    

     
    while(left < right){
     
    
   

    

     

    
    

     

              mid = left + (right - left) / 2;
     
    
   

    

     

    
    

     
        if(nums[mid] > target){
     
    
   

    

     

    
    

     
        //因为插入的数要么在left和right之间，要么在两者之上
     
    
   

    

     

    
    

     
        //如果是right = mid - 1, 可能会比要查找的数小，那么插入的位置在right之后，这样就容易混乱
     
    
   

    

     

    
    

     

                  right = mid;
     
    
   

    

     

    
    

     

              }else if(nums[mid] < target){
     
    
   

    

     

    
    

     
        //left还是left = mid + 1,因为如果此时left大于目标值下标，也是第一个大于它的数
     
    
   

    

     

    
    

     

                  left = mid + 1;
     
    
   

    

     

    
    

     

              }else{
     
    
   

    

     

    
    

     
            return mid;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    //没有找到目标值
     
    
   

    

     

    
    

     
    //插入的位置，从left下标考虑，所以上面的right才写成right = mid,不然还需要多考虑right的情况
     
    
   

    

     

    
    

     
    //nums[left] == target表示只有一个元素的特殊情况
     
    
   

    

     

    
    

     
    if(nums[left] >= target){
     
    
   

    

     

    
    

     
        return left;
     
    
   

    

     

    
    

     

          }else{
     
    
   

    

     

    
    

     
        return left + 1;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

【敲黑板】：之所以写成mid = left + (right - left) / 2, 而不是mid = (left + right) / 2, 是因为left + right做的是加法运算可能会超出int范围。 

复杂度分析

时间复杂度：O(logN)

空间复杂度：O(1)

结语 

今天是力扣打卡第5天！

笔者会一直坚持下去的，和铁汁们一起加油，互相监督哦。

加油加油，咱们明天再见！！

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121128815