题目描述

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

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

样例

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

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

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

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

算法1

(二分查找) $O(logn)$

题目给到的数组是一个排序数组,排序数组具有明显的单调性。在有单调性的问题中查找答案，可以使用二分查找。

解析题目：
从数组中找到一个i 位置,使得target > nums[i] 的位置,以这个位置作为分界点
左边:nums[i] < target ; 右边: target <= nums[k] , i < k <= nums.length - 1.

转化问题: 找到第一个target <= nums[i] 的位置
二分性质: target <= nums[i]

时间复杂度

参考文献

Java 代码

public class 搜索插入位置 {
    public int searchInsert(int[] nums, int target) {
        //验证特殊情况
        if(nums.length == 0 || nums[nums.length - 1] < target) return nums.length;

        //定义左右边界: 插入的位置只能是在数组的长度范围内
        int left = 0, right = nums.length - 1;

        while(left < right){
            int mid = left + right >> 1;
            //所以当target <= nums[mid],right = mid,因为mid 位置有可能是答案
            //当nums[mid] < target ,left = mid + 1,此时的mid //位置一定不是答案,所以直接跳过

            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}