二分法

1. 整数二分查找(O(logn))

1.1. 不可重复数列二分查找

// A[] 为不重复递增数列，x 为需要查找的值
int binarySearch(int A[], int left, int right, int x){
    int mid;
    while(left<=right){
        mid=left+(right-left)/2; // 防止溢出
        if(A[mid]==x) return mid;
        else if(A[mid]>x) right=mid-1;
        else left=mid+1;
    }
    return -1;
}

1.2. 可重复数列二分查找

假设目标值 x 分布在 [L, R) 之间，则可分别查找 L 和 R

// A[] 为可重复递增数列，查找第一个大于等于 x 的数
int lower_bound(int A[], int left, int right, int x){
    int mid;
    while(left<right){// left==right 时，找到唯一位置
        mid=left+(right-left)/2;
        if(A[mid]>=x) right=mid;
        else left=mid+1;
    }
    if(A[right]>=x) return left;
    else return -1;
}

// A[] 为可重复递增数列，查找第一个大于 x 的数
int upper_bound(int A[], int left, int right, int x){
    int mid;
    while(left<right){
        mid=left+(right-left)/2;
        if(A[mid]>x) right=mid;
        else left=mid+1;
    }
    if(A[right]>x) return left;
    else return -1;
}

1.3. 寻找可重复数列中满足条件 C 的元素位置

查找可重复数列中满足条件 C 的元素位置可以分解为

• 查找第一个满足条件 C 的数 L
• 查找第一个满足条件 C 的数起，第一个不满足条件 C 的数 R
• 满足条件 C 的元素位置为 [L, R)

// A[] 为可重复递增数列，查找第一个满足条件 C 的数
int lower_bound(int A[], int left, int right){
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(C(mid)) right=mid;
        else left=mid+1;
    }
    if(C(right)) return left;
    else return -1;
}
// 查找第一个满足条件 C 的数起，第一个不满足条件 C 的数
int upper_bound(int A[], int left, int right){
    left=lower_bound(A, left, right);
    if(left==-1) return -1;
    else(left==right) return right+1;
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(!C(mid)) right=mid;
        else left=mid+1;
    }
    return left;
}

2. 二分法拓展

将二分查找的范围从整数拓展到实数时，判断是否找到需要考虑精度。

// 求实数范围 [left, right] 上，递增函数 f(x)=0 的解
double solve(double left, double right){
    const double eps=1e-5;
    while(right-left<eps){
        mid=(left+right)/2;
        if(f(x)>0) right=mid; // f(x) 递减，则改为 <0
        else left=mid;
    }
    return mid;
}

3. 快速幂

给定三个正整数 $a,b,m\ (a<10^9,b<10^18,1<m<10^9)$ ，求 $a^b\%m$

循环写法（O(b)）

typedef long long LL;
LL power(LL a, LL b){
    a%=m;
    LL ans=1;
    for(int i=0;i<b;i++){
        ans=ans*a%m;
    }
    return ans;
}

递归写法（O(logb)）

typedef long long LL;
LL power(LL a, LL b){
    a%=m;
    if(b==0) return 1; // b=0 时，a^0=1
    // b 为奇数，转换为 b-1
    if(b%2==1) return a*power(a,b-1,m)%m;
    else {// b 为偶数，转换为 b/2
        LL mul=power(a,b/2,m);
        return mul*mul%m;
    }
}

迭代写法（O(logb)）

typedef long long LL;
LL power(LL a, LL b){
    a%=m; 
    LL ans=1;
    while(b>0){
        if(b&1){// 若 b 的二进制末位为1，则 true(等于 b%2)
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1; // 将 b 的二进制右移1位(等于 b/=2)
    }
    return ans;
}

4. ChangeLog

2018.09.03 初稿