[力扣_35] 搜索插入位置

题目入口:点击进入

相关算法:

  • 二分搜索——时间复杂度O(logn),空间复杂度O(1)

思路和算法:

这是一道简单题,思路也不难,正好可以借着这道题去理解下二分查找,大家可以看看大佬的文章《liweiwei》,会很帮助,这道题的思路和寻常的二分并没有太大区别。

二分搜索

根据题意,在nums[mid]==target的时候,代表数组中存在此值,直接返回target即可,而题目中所说的给出插入位置,那么我们就可以将循环条件定位left<=right,当循环结束后,直接返回left即可,因为循环结束后,这是个空区间,不包含任何数值,而left恰好就是其插入位置,如下图所示:

img此时nums[mid] > target
收缩右边界
right = mid -1

img此时nums[mid] < target
收缩左边界
left = mid + 1

img此时代表target不在序列中
返回left即可。

代码如下所示:

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

本文链接:

https://nullcode.fun/82.html
1 + 1 =
快来做第一个评论的人吧~