关于程序员:PAT二分模板

1. 寻找指定元素是否存在

int binarySearch(int A[], int left, int right, int x){
    int mid;
    while(left <= right){mid = (left + right) / 2;
        if(A[mid] == x) return mid;
        else if(A[mid] > x) right = mid - 1;
        else    left = mid + 1;
    }
    return -1;
}

2. 已知答案肯定存在，寻找其地位

寻找有序序列第一个满足某条件的元素的地位（满足条件的都在左边），留神区间必须能笼罩解的所有可能取值。同理，若找最初一个满足某条件的，能够找第一个不满足该条件的，最初位序减一即可。
此模板若设置一个特定的值来代表不存在解的状况，即可取代上一个模板来用。

int solve(int left, int right){
    int mid;
    while(left < right){// 此处没有等号，因为取等号时就代表着曾经确定了最终答案
        mid = (right + left) / 2;
        if(条件成立)    right = mid;    // 往左找
        else    left = mid+1;   // 往右找
    }
    return left;
}

3. 拓展利用：疾速幂的递归写法

// 上面为疾速幂的递归写法
//a^b%m
typedef long long LL;
LL binaryPow(LL a, LL b, LL m){
    // 幂为 0 间接为 1
    if(!b)  return 1;
    // 该写法判断奇数较为简洁，转换为 a *a^(b-1)%m
    if(b&1) return a * binaryPow(a, b-1, m) % m;
    // 留神上面肯定要先求出 binaryPow(a, b/2, m)，再求积，不然工夫复杂度又回去了
    else{LL mul = binaryPow(a, b/2, m);
        return mul * mul % m;
    }
}