二分查找、二分边界查找算法的模板代码总结-Java实现

二分查找是一种常用的查找算法，也是解决很多查找类题目的常用方法，它可以达到 O(log n)的时间复杂度。

一般而言，当一个题目出现以下特性时，你就应该立即联想到它可能需要使用二分查找：

1. 待查找的数组有序或者部分有序; 2. 要求时间复杂度低于 O(n)，或者直接要求时间复杂度为 O(log n)

二分查找有很多种变体，使用时需要注意查找条件，判断条件和左右边界的更新方式，
三者配合不好就很容易出现死循环或者遗漏区域，本篇中我们将介绍常见的几种查找方式的模板代码，包括：

1.标准的二分查找
2.二分查找左边界
3.二分查找右边界
4.二分查找极值点

1.标准的二分查找:

首先给出标准二分查找的模板：

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

这里有几点需要注意：

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

 1. left/mid , right (left, mid 指向同一个数，right指向它的下一个数)
 2. left / mid / right （left，mid，right 指向同一个数）

即因为 mid 对于长度为偶数的区间总是偏左的，所以当区间长度小于等于2时，mid 总是和 left 在同一侧。