搜索插入位置-力扣35（数组-二分查找）

﹏ヽ暗。殇╰゛Y 2023-01-13 01:40 184阅读 0赞

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

你可以假设数组中无重复元素。

示例 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/problems/search-insert-position  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路：这道题很简单，首先可以想到的是遍历，但是如果遍历的话，时间复杂度是O(n)，其实可以采用二分查找解决这个问题，这样就用到了题目中的“排序”数组这个条件。下面是标准的二分解题的框架：

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

--------------------

注意：  
上面二分查找的时候采用的是 int mid = left + (right - left)/2;为什么此处不直接采用(right+left)/2，其实这主要是为了避免当二分上界超过int型数据范围的一半，那么当查询的元素在序列较后的位置时，(left+right)/2中的left+right会超过int导致溢出，所以采用left + (right - left)/2这种形式就是为了避免这个问题。

另外一个问题就是left + (right - left)>>1为什么与left + (right - left)/2是不等价的，这是因为>>与<<的优先级低于+，所以不等价。int mid = ((right - left) >> 1) + left;与int mid = left + (right - left)/2;才是等价的。