C++刷题笔记(六)——二分模板/快速幂/欧几里得

1.二分法模板

参考资料：二分查找模板总结

二分法的应用场景，主要可以分为以下四种：

1. 数组有序，且不包含重复元素
2. 数组有序，但包含重复元素
3. 数组部分有序，且不包含重复元素
4. 数组部分有序，且包含重复元素

1.1 针对情况一：标准二分查找

这也是最简单的一种情况，STL库里的二分实现也是基于这种标准的实现

但缺点是无法处理元素重复的问题 

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;
    }
}

1.2 针对情况二三四：二分查找边界

以下查找边界的方法当然也可以用来处理 情况一

1.2.1 寻找区间左边界

例如在情况二下需要寻找 重复 x 的区间

以下模板中的，寻找第一个 >= x 的数，即是在寻找 重复 x 的 区间的左边界

// 寻找第一个大于等于x的数
int lower_bound(int target){
    int l = 0,int r = n - 1;
    while(l < r){
        int mid = l + (r-l)/2;//防止溢出
        // 说明第一个 >=x的元素一定在mid或mid左边
        // 右边界变小,往左半区间寻找
        // ( check(mid) )
        if(num[mid] >= target){
        // 若满足 说明满足目标的左边界会在mid左边
        // 所以移动r
            r = mid;
        }
        else l = mid + 1;
    }
    // l = r时退出循环 返回哪个都行
    return l;
}

在整个数组中都未找到一个 >= x 的数时，r 和 l 最终都会落在数组的最末位（ 即下标 n - 1 处）

一个小细节，当取 r = n 时，以上二分的主体过程并不会受影响

改变的只有 r 和 l 的最终位置：数组的最末位的下一位

（但这种写法数组容易越界 需要注意打补丁）

但这个方法针对 lc 35： 搜索插入位置   的情景就非常方便，例如样例3

1.2.2 寻找区间右边界

例如 找到满足 >=nums[0] 的右边界值，相较于以上寻找左边界的模板，有以下三个变化：
1. mid 的取值        2.满足check(mid)条件下的 l 与 r 的取值

    public int upper_bound(int[] nums,int target){
        int l = 0,r = nums.le