35. 搜索插入位置

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

题例

示例1

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

示例2

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

示例3

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

示例4

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

分析

题目给出的数组是一个排序数组，而且必须使用时间复杂度为O(log_n)的算法，所以我们选用二分查找1。

实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0 ;
        int right = nums.length-1;
        //特殊处理
        if(nums[right]<target) return right+1;
        while(left<right){
            //下取整缩小左区间
            int mid = (right+left)>>>1;
            if(nums[mid]<target) left = mid+1;
            else right = mid;
        }
        return left;
    }
}

说明

这道题寻找插入目标值的位置无非4种情况

• 目标值在所有元素的前面
• 目标值等于某一个元素
• 目标值在某两个元素之间
• 目标值在数组最后

首先在进入循环的时候做一次特殊处理，判断是否是第四种情况。

if(nums[right]<target) return right+1;

我们采用二分排除法，如果不是第四种情况的话， 那么我们在循环中需要考虑的区间判断就会简单很多了。
可以把插入位置的区间分为两个部分，一部分为必不可能存在插入位置的区间，一部分为存在插入位置的区间。我们只需要不断排除掉必不可能存在插入位置的区间，最终定位的区间位置就是可以插入的位置。所以进入循环体只需要考虑插入位置是否在(mid,right]这个区间内

if(nums[mid]<target)

如果在这个区间的话 那么[left,mid]这个区间就可以排除掉了，相反，如果不在这个区间内，那么我们也可以排除掉(mid,right]这个区间，逐渐缩小范围，最终留下的区间就是元素插入的位置。