力扣 35.搜索插入位置

1.题目描述

力扣 35.搜索插入位置

2.思路讲解

看到了时间复杂度要求,一股很浓的二分算法味儿就来了

如果只是简单的搜索返回位置,那么题目就没啥意思了,唯一难点就是怎么返回要插入的位置

插入位置肯定是前面小于目标值,后面大于目标值,用这个作为条件,返回我们位置

当然这个算法没法保证第一个位置及0,和最后一个位置,所以我们需要去做一个特判

3.代码展示

int searchInsert(int* nums, int numsSize, int target){
   int left=0;
   int right=numsSize-1;
   int mid=0;
   if(target<nums[0])
   {
       return 0;
   }
   else if(target>nums[numsSize-1])
   {
       return numsSize;
   }
   while(left<=right)
   {
       int mid=left+(right-left)/2;
       if(nums[mid]==target)
       {
           return mid;
       }
       else if(nums[mid]>target&&nums[mid-1]<target)
       {
           return mid;
       }
       else if(nums[mid]>target)
       {
           right=mid-1;
       }
       else
       {
           left=mid+1;
       }
   }
   return;
}

4.总结

题目难度不大,最近期末考试,考试周导致我最近没多少时间做题,希望考完以后,能好好做一天题

上一篇:python列表推导式_鸡兔同笼


下一篇:跨域