35. 搜索插入位置——二分查找模版

一、题目

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

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

示例 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

二、解答

2.1 方法一：顺序查找

public int searchInsert(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++){
            if (nums[i] >= target){
                return i;
            }
        }

        return nums.length;
    }

2.2 方法二：二分查找

public int searchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r){
            int mid = (l+r)/2;
            if (target == nums[mid]){
                return mid;
            }else if (target >nums[mid]){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }

2.3 方法三：二分查找优化+模版

2.3.1 优化点

int mid = (l+r)/2; 其中l+r可能产生溢出

• 优化方案一：int mid = l + (r - l) / 2 ;能减少溢出的概率，但不能避免。
• 完美方案：int mid = (left + right) >>> 1 ;

循环可以进行的条件写成 while (left <= right) 时，在退出循环的时候，需要考虑返回 left 还是 right。

• 本例子中的思考

// 对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
// 在上面的 while (left <= right) 退出循环以后，right < left，right = 0 ，left = 1
// 根据题意应该返回 left，
// 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right

• 优化方案：首先把循环可以进行的条件写成 while(left < right)，在退出循环的时候，一定有 left == right 成立，此时返回 left 或者 right 都可以。

2.3.2 模版

public int searchInsert(int[] nums, int target) {
        int len = nums.length;

        if (len == 0) {
            return 0;
        }

        int left = 0;
        int right = len;

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

针对本例优化代码为

public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        if (nums[len - 1] < target) {
            return len;
        }
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid =  (left + right) >>> 1;
            if (nums[mid] < target) {
                // nums[mid] 的值可以舍弃
                left = mid + 1;
            } else {
                // nums[mid] 不能舍弃
                right = mid;
            }
        }
        return right;
    }