算法：对二分查找法的理解

以下是使用二分法初期经常懵的点，根据自己的理解做出解答：

解答基于LeetCode 35.搜索插入位置

1.left~right区间应该是开区间还是闭区间
答案：

• 其实这个区间的含义是“搜索区间”，而搜索的数组元素只在0~nums.length-1位置上，那么这个区间只包含所有元素，即可以是左闭右闭(left=0,right=nums.length-1)或者是左闭右开(left=0,right=nums.length)[为什么不使用什么left=-1这种，感觉是因为太奇怪了？]
• 使用左闭右开的好处是可以直接从区间本身得到返回结果，因为本题（35.搜索插入位置）的返回结果可以是0~nums.length，但若是使用左闭右闭，其实从区间本身是得不到nums.length这个位置的，所以使用了左闭右开
• 而又为什么也有用左闭右闭这种不能从本身直接得到结果的方法呢，因为这样子对称，看起来比较舒服（没错！）

2.循环条件应该是“left <= right”还是“left < right”
答案：

• 由区间定义决定
• 如果是“左闭右闭”，那么是可能出现left==right的情况，因为比如[1,1]，区间内还有一个元素，那需要进行比较
  • 这个比较可以在循环内做（那么就需要left <= right）
  • 如果想独立出在循环外做（那么就只需要left < right）也ok，只是需要在外面多写一次比较
• 而如果是“左闭右开”，那么是不需要考虑left==right这种情况的，因为比如[1,1)里面压根没有元素

3.中间元素下标的取值应该向上还是向下
答案：

• 看你喜欢。不过得注意不同的方法在“左闭右闭”和“左闭右开”中的适用性，“左闭右开”中如果向上取的话有可能会偏右，自己举个例子就知道了
• 注意不要使用middle = Math.floor((left+right) / 2)，因为left和right肯定不超过整数最大值，但left+right就不一定了
• 可以使用middle = left + Math.floor((right - left) / 2)或者middle = right - Math.floor((right - left) / 2)，向上还是向下自己举例子看看

4.比较target和中间元素得到的结果应该得让left和right的位置怎么迁移
答案：

• 区间定义为“区间左边的元素都小于target，区间右边的元素都大于target”
• 由“左闭右闭”或者“左闭右开”决定
• 如果是“左闭右闭”，如下图
  
  • 当 target=6 时，中间元素5小于target，应该迁移left，让“区间左边的元素都小于target”，而left位置是不属于区间左边的，所以left = middle + 1
  • 当 target=4 时，中间元素5大于target，应该迁移right，让“区间右边的元素都大于target”，而right位置是不属于区间右边的，所以right = middle - 1
• 如果是“左闭右开”，如下图
  
  • 同上。当 target=6 时，中间元素5小于target，应该迁移left，让“区间左边的元素都小于target”，而left位置是不属于区间左边的，所以left = middle + 1
  • 当 target=4 时，中间元素5大于target，应该迁移right，让“区间右边的元素都大于target”，但跟上面不同的是，这里是“左闭右开”，所以right所在位置其实是属于区间右边。“区间右边的元素都大于target”，right所在位置的元素应该大于target，而nums[middle]大于target，所以right = middle