二分查找右边界模板

二分查找作为程序员的一项基本技能，是面试官最常使用来考察程序员基本素质的算法之一，也是解决很多查找类题目的常用方法，它可以达到  的时间复杂度。有了寻找左边界的分析之后，再来看寻找右边界就容易很多了，毕竟左右两种情况是对称的嘛。

二分寻找左边界模板可以参考https://blog.csdn.net/justidle/article/details/104304725这篇文章。

前提条件

必须有序。一般是从小到大有序。

坑点

计算中间值导致的数据越界。一般我们都是定义左边界（left）和右边界（right）都使用 int 类型，如果 left 和 right 足够大，mid = (left + right)/2，可能会由于 left+right 导致 int 数据类型越界。所以安全的写法是 mid = left + ((right - left) >> 1) 或者 mid = left + (right - left) / 2，推荐使用右移操作，因为右移比除法快。

模板代码

C++模板

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

程序解读

1、循环条件： left < right 。

2、中间位置计算： mid = left + ((right -left) >> 1) + 1 。中间位置的计算变了，我们在末尾多加了1。这样，无论对于奇数还是偶数，这个中间的位置都是偏右的。从对称的角度看，寻找左边界的时候，中间位置是偏左的，那寻找右边界的时候，中间位置就应该偏右。根本原因是，在最后 left 和 right 相邻时，如果 mid 偏左，则 left，mid 指向同一个位置，right 指向它们的下一个位置，在 nums[left] 已经等于目标值的情况下，这三个位置的值都不会更新，从而进入了死循环。所以我们应该让 mid 偏右，这样 left 就能向右移动。

3、左边界更新：left = mid 。

4、右边界更新： right = mid - 1 。

5、返回值： nums[right] == target ? right : -1 。