【Java练习题】搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例 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

解题思路
题目告诉你“排序数组”，其实就是在暗示你用二分查找法, 二分查找法的思想并不难，但写好一个二分法并不简单。

public class Solution3 {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (nums[len - 1] < target) {
            return len;
        }

        int left = 0;
        int right = len - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            // 等于的情况最简单，我们应该放在第 1 个分支进行判断
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 题目要我们返回大于或者等于目标值的第 1 个数的索引
                // 此时 mid 一定不是所求的左边界，
                // 此时左边界更新为 mid + 1
                left = mid + 1;
            } else {
                // 既然不会等于，此时 nums[mid] > target
                // mid 也一定不是所求的右边界
                // 此时右边界更新为 mid - 1
                right = mid - 1;
            }
        }
        // 注意：一定得返回左边界 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

        return left;
    }
}

Java
int mid = (left + right) / 2
这行代码是有问题的，在 left 和 right 都比较大的时候，left + right 很有可能超过 int 类型能表示的最大值，即整型溢出，为了避免这个问题，应该写成：

Java
int mid = left + (right - left) / 2 ;
事实上，int mid = left + (right - left) / 2 在 right 很大、 left 是负数且很小的时候， right - left 也有可能超过 int 类型能表示的最大值，只不过一般情况下 left 和 right 表示的是数组索引值，left 是非负数，因此 right - left 溢出的可能性很小。

public class Solution {

    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 - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

更好的写法是：

Java
int mid = (left + right) >>> 1 ;

int mid=(left+right)>>>1与 int mid=(left+right)/2有什么区别

>>>是右移运算，在计算机中是一种运算操作，但是他的运算结果正好能对应一个整数的二分之一值，这就正好能代替数学上的除2运算，但是比除2运算要快。

(1)如果 left 和 right 表示的是数组的索引，就要考虑“索引是否有效” ，即“索引是否越界” 是重要的定界依据；

左右边界一定要包括目标元素，当 target 比数组中的最后一个数字还要大（不能等于）的时候，插入元素的位置就是数组的最后一个位置 + 1，即 (len - 1 + 1 =) len，如果忽略掉这一点，把右边界定为 len - 1 ，代码就不能通过在线测评。

(2)中位数先写int mid = (left + right) >>> 1 ; 根据循环里分支的编写情况，再做调整理解这一点，首先要知道：当数组的元素个数是偶数的时候，中位数有左中位数和右中位数之分。

当数组的元素个数是偶数的时候：
使用 int mid = left + (right - left) / 2 ;得到左中位数的索引；

使用int mid = left + (right - left + 1) / 2 ; 得到右中位数的索引。

当数组的元素个数是奇数的时候，以上二者都能选到最中间的那个中位数。
其次，

int mid = left + (right - left) / 2 ; 等价于int mid = (left + right) >>> 1；

int mid = left + (right - left + 1) / 2 ; 等价于int mid = (left + right + 1) >>> 1;
记忆方法：

(right - left) 不加 1 选左中位数，加 1 选右中位数。

public class Solution {

    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 - left) >>> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}