二分法的各种灵魂拷问

二分法，很简单啊，很早就知道这个了，不就是一直从中间取值，然后找到target吗

那么， 每次写二分法时，有没有想过，while判断条件里的left和right，究竟是<还是<=呢；更新边界时，right究竟是middle还是middle - 1呢？

至少对我来说，每次写二分这些都是随缘的，能a就行，但是大部分时候a不了

回到正题，写二分法时，最重要的就是保持区间不变

所谓区间不变，就是整个算法当中，都要明确自己的代码是左闭右闭[left, right]，还是左闭右开[left, right)，以下只会讲左闭右闭的情况，另外的情况就很简单了。

< 还是 <=

while里的判断条件，也就是区间是否合法的条件，我们假设left和right相等，区间就是[1,1]，这个区间显然合法，所以应该是<=

也不难想到，在左闭右开的情况下，是不能取等号的，因为[1, 1)显然不合法

要不要减一（加一）

边界更新的前提是我们已经知道了nums[middle] != target， 此时我们的下一个搜索范围，肯定不应该包含middle了，所以应该是要加一或减一的。

于是，我们就有了基于左闭右闭区间的二分查找代码

while (left <= right) {
    int middle = left + (right - left) / 2; //这么写是为了防止int爆掉
    if (nums[middle] > target) right = middle - 1;
    else if (nums[middle] < target>) left = middle + 1;
    else return middle; //找到target了
}
return -1; //没有找到