二分查找模板

标准二分查找的模板：

class BinarySearch {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

循环条件： left <= right
中间位置计算： mid = left + ((right -left) >> 1)
左边界更新：left = mid + 1
右边界更新： right = mid - 1
返回值： mid / -1

这里有几点需要注意：

我们的循环条件中包含了
1、left == right的情况，则我们必须在每次循环中改变 left 和 right的指向，以防止进入死循环
2、循环终止的条件包括：
（1）找到了目标值
（2）left > right （这种情况发生于当left, mid, right指向同一个数时，这个数还不是目标值，则整个查找结束。）
3、left + ((right -left) >> 1) 其实和 (left + right) / 2是等价的，这样写的目的一个是为了防止 (left + right)出现溢出，一个是用右移操作替代除法提升性能。
4、left + ((right -left) >> 1) 对于目标区域长度为奇数而言，是处于正中间的，对于长度为偶数而言，是中间偏左的。因此左右边界相遇时，只会是以下两种情况：

（1）left/mid , right (left, mid 指向同一个数，right指向它的下一个数)
（2）left/mid/right （left, mid, right 指向同一个数）
即因为mid对于长度为偶数的区间总是偏左的，所以当区间长度小于等于2时，mid 总是和 left在同一侧。