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