需要知道的一些小技巧
以搜索区间为[0, len -1]为例子
左中位数下标数: (0 + len - 1) >>> 1
右中位数下标数: (0 + len - 1 + 1) >>> 1
左中位数为第k个: (len + 1) >>> 1
右中位数为第k个: (len + 1 >>> 1) + 1
其实，我们如果明白左中位数为第k个的公式是怎么得出来的，其他的就也都明白了。
- 当数组个数（设为len）为奇数时，len / 2会得到一个小数，但是因为向下取整，所以小数部分并没有用，所以我们得到的其实是比中位数偏左的一个数。但是如果我们将len加上一使其len = len + 1变为偶数，那么len / 2结果就会比之前的结果多一，也就是说，现在得到的数就是中位数。那右中位数在左中位数的k上加一即可得到。
- 当数组个数为偶数时，len >>> 1和 len + 1 >>> 1并无区别，得到的显然是左中位数了。
右中位数也就是(len >>> 1) + 1
既然我们能够计算出左中位数为第k个，那我们如果想计算下标数，只需k - 1即可，即
((len + 1) >>> 1) - 1 -> (len - 1) >>> 1
其实以上说的并不是很容易理解记住，我们在计算中位数的时候可以先尝试举几个例子，然后再写公式。我是通过记住下标的公式，求个数的时候加一即可。
关于二分查找的模版
// 这样选取的是在最左侧出现的target
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length - 1; // 这里是len-1还是len取决于具体的问题
while (l < r){ // 这里写作< 表示当l==r时，我们认为查询结束 但是l==r这个区间中其实是有一个值的 所以如果目标中不一定存在nums中，我们需要验证nums[r]是否=target
int mid = l + (r - l) / 2; // 根据下面的逻辑(left进行加一操作)决定选择左中位数
if (target > nums[mid]){ // 左侧边界不会跳过任何一个=target的元素，保证target一定在其右侧或其指向target
l = mid + 1;
}
else{ //不断收缩右侧边界，保留找到的target并持续向左收缩（找到nums第一个出现的target）
r = mid;
}
}
return r;
}
}
// 这样选取的是在最右侧出现的target
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l < r){
int mid = l + (r - l + 1) / 2; // 根据具下面的逻辑(right进行减一操作)决定选择右中位数
if (target < nums[mid]){ // 右侧边界不会跳过任何一个=target的树，保证target一定在其左侧或其指向target
r = mid - 1;
}
else{ //不断收缩左侧边界，保留找到的target并持续向右收缩（找到nums最后出现的target）
l = mid;
}
}
return r;
}
}
有几点需要注意
- 判断条件为<而非<=
- 边界更新，如果l = mid + 1，则mid = l + r >>>1即使用左中位数。反之，如果r = mid - 1，则mid = l + r + 1 >>> 1即选用右中位数，因为如果中位数选取的不对，可能会陷入死循环。具体的边界选取要根据题意进行判断，再写出边界更新之后 再根据其去选择是用左中位数还是右中位数。
- 有些时候问题会出现一些变形，那么就需要具体情况具体分析了
边界可能并不是从0 - len - 1，可能是从0 - len；
目标数组nums中并不一定存在target，这种情况下需要判断nums[r]是不是等于target
要求找到第一个target或最后一个target，需要对模版进行选择
可能你会好奇，为什么要根据边界更新来选择中位数，为什么找第一个target和最后一个target可以通过不同的模版实现，下面我们就讲一下这个问题。
二分法的本质是对区间进行操作，每一次查找去掉（一半）无用的区间
如果我们想找到第一个target， 那么我们就应该不断缩小右侧，同时保证target始终在区间中。
我们分开讲这两个过程：缩小、保证
- 缩小：当我们找到一个target之后，这个target的右侧的元素就不再是我们考虑范围内的了，虽然当前找到的target的右侧也可能有满足条件的元素，但因为我们要找的是第一个，也就是最左侧的，所以右侧的就不重要了。
- 保证target在区间中：我们应该用right保留下来当前这个target 即让right = nums[mid]；
那么什么时候是满足条件的呢？当 nums[mid] >= target时，这个nums[mid]就可能满足条件（当然target可能并不是确定的数字 具体问题需要具体分析）。那么显然当 nums[mid] < target时，这个nums[mid]就是一定不满足条件的，应该被排除，所以left = mid + 1
如果想找最后一个target，也是相同的原理，可以自己分析一下
到这里，我们就讲完了为什么找第一个target和最后一个target可以通过不同的模版实现，下面我们讲一下为什么要根据边界更新来选择中位数。
我们还是以找第一个target为例
通过以上，我们可以概括出一句话左边界负责找到满足条件的范围，右边界负责收缩
我们采取反证法：如果取右中位数，那么考虑只剩两个元素的时候。如果nums[mid]满足条件，那么自然有right=mid，而因为是右中位数，所以right就是mid。显然，此时无法收缩了（所以模版要求这么做 谁=mid + 1就应该用哪个中位数）。
其内在原理是，left和right总是一个负责排除，一个负责收缩。
举个例子，当我们使用left去排除，即left = mid + 1， 那么right必然是收缩 right = mid，这时我们使用左中位数可以保证不管是排除还是收缩，区间都会变小（排除不用说了，肯定会变小；收缩的话至少也会将右中位数收缩掉）。反之，如果使用右中位数，那么收缩的时候区间可能不会变小（即上面说的只剩两个元素的情况）。
所以我们才选择使用左中位数，因为这样右边界才总能收缩到第一个满足条件的元素
现在再来我们试想 即使我们一开始找到的是一个大于target的数字 是不是边界不断收缩 最终找到的还是第一个满足条件的元素。
下面是我总结的一些题目要求及对应的解法
- 若题目中明确说明输入的数组一定包含要找的目标值target 那么 l = 0; r = nums.length - 1; return r当然也可以return l 因为l = r
- 若题目中的输入数组中不一定含有要找到目标值target,那么大体可以划分成一下几个情况
1）若不存在要求返回-1 那么 l = 0; r = nums.length - 1; 在循环结束后 需要判断nums[right] 是否=target，若是就按照题目要求返回 不是就返回-1
2）若不存在要求返回它应该在的位置(第一个比target大的数的位置) 那么 l = 0; r = nums.length(如果target比nums中所有元素都大 那么他返回的index应该是nums.length) 。而且在这种情况下 应选择使用左中位数。
3）若不存在要求返回第一个比他小的数的位置 那么l = -1(如果target比nums中所有元素都小 那么他返回的index应该是-1); r = nums.length-1 在这种情况下 选择使用右中位数。
