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