LeetCode35. 搜索插入位置

• 一、题目
• • 1、题目描述
  • 2、基础框架
  • 3、原题链接
• 二、解题报告
• • 1、思路分析
  • 2、复杂度分析
  • 3、代码详解

 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 请必须使用时间复杂度为 O(log n) 的算法。

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

35. 搜索插入位置

1. 方法：二分查找

• 条件：有序数组
• 思想：先将被查找的数和数组的中间键对应的 v a l u e value value 比较，因为数组是有序的，所有若被查找的数小于数组的中间键对应的 v a l u e value value 则这个数则在数组的左部分,然后将中间键的左边数组当作一个数组来进行二分查找。反之，则在数组的右部分，若相等，则查找成功。
• 优点：只需 O ( l o g n ) O(logn) O(logn) 步便可查找完成。

2. 思路

• 考虑这个插入位置 p o s pos pos，它的成立条件：
  n u m s [ p o s − 1 ] < t a r g e t ≤ n u m s [ p o s ] nums[pos-1] 其中 n u m s nums nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 p o s pos pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 t a r g e t target target 的下标」。

• 具体实现：
  • 终止条件： l e f t > r i g h t left > right left>right；
  • 返回值： a n s ans ans；存在两种情况，一是在下标 [ 0 , n u m s S i z e − 1 ] [0,numsSize-1] [0,numsSize−1] 中可以找到插入位置， a n s ans ans 值为 l e f t = r i g h t left = right left=right 时的下标；二是找不到插入位置， a n s ans ans 值为 s u m s S i z e sumsSize sumsSize;；
  • m i d = ( ( r i g h t − l e f t ) > > 1 ) + l e f t mid = ((right - left) >> 1) + left mid=((right−left)>>1)+left 用来寻找中间键 m i d mid mid；
  • r i g h t = m i d − 1 right = mid - 1 right=mid−1 和 l e f t = m i d + 1 left = mid + 1 left=mid+1 防止陷入判断死循环；

• 时间复杂度： O ( l o g n ) O(logn) O(logn)，其中 n n n 为数组的长度
• 空间复杂度： O ( 1 ) O(1) O(1)，只需要常数空间存放若干变量

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