简单的二分查找

前提：数组有序（可先排序），无重复数组（可单独处理）

1. 一般使用左闭右开区间，感觉代码容易一点点，不要记太多的套路，直接一套带走，左闭右开

2. 二分查找特别需要注意左右的区间: 这里很容易写错，所以最好的办法是在纸上画一个数组，要记住边界的限定，时刻在心中默念，左闭右开无等号，有闭有加，无闭无加 
while (left < right)//无等号

left = mid + 1;//左闭


right = mid; //右开

3. 最后一点就是middle的值了，这里需要注意一点的就是，防止超出int类型的最大值，只需要记住，防超出用减号： 
 int mid = left + ((right - left) / 2)

左闭右闭：

  1. while(left <= right), 因为当left == right 的时候是有意义的

  2. if(nums[middle] > target), right要赋值为middle-1，因为当前这个nums[middle] 一定不是target，那么接下来要查找的左右区间结束下标位置就是middle-1


代码：左闭右闭区间 

左闭右开：[left, right)
class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1; //左闭右闭
        }
        return -1;
    }
}

  1. while(left < right), 使用<， 因为left==right在区间中是没有意义的

  2. if(nums[midlle] > target), right 更新为middle, 因为当前nums[middle]不等于target， 去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle, 即：下一个查询区间不会去比较nums[middle]

代码：左闭右开区间 

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {//左闭右开区间
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid; //左闭右开区间
        }
        return -1;
    }
}