关于程序员: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;
    }
}