算法笔记(5)| 二分

1.二分查找

二分查找是基于有序序列的查找算法，该算法一开始令[left,right]为整个序列的下标区间，然后每次测试当前的[left,right]的中间位置mid=(left+right)/2，判断A[mid]与想要查询的元素x的大小，如果A[mid]==x，则说明查找成功；如果A[mid]>x，则说明结果偏大，需要往左半边查找；如果A[mid]<x则说明结果偏小，需要往右半边查找。

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 if(A[mid]<x){
            left=mid+1;
        }
    }
    return -1;  //查找失败
}

二分查找的时间复杂度是O(logn)，相比于顺序查找的O(n)，是要优秀许多的。

现在假设递增序列A中的元素可能重复，那么对于给定的查询元素x，求出：

1.求出序列中第一个大于等于x的元素的位置L

//left=0 right=n(注意不是n-1)
int lower_bound(int A[],int left,int right,int x){  //对于元素x，就算不存在于A中，也可以返回所需要的值
    int mid;
    while(left<right){  //left==right意味着找到了唯一的位置
        mid=(left+right)/2;
        if(A[mid]>=x){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;  //返回查找的位置(当left==right时，循环停止，所以此时left=right)
}

2.求出序列中第一个大于x的元素的位置

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

综上，从上述两个问题中可以得出寻找有序序列中第一个满足某条件的元素的位置这一类题目的解题模板：

//解题模板
//二分区间为[left,right]，范围是[0,n]
int solve(int A[],int left,int right,int x){
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(满足的条件){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}


//寻找最后一个满足条件C的元素的位置模板
int solve(int A[],int left,int right,int x){
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(满足的 !C 条件){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left-1;
}

2.二分拓展

1.给定一个定义在[L,R]上的单调函数f(x)，求方程f(x)=0的根

const double eps=1e-5;  //精度

double f(double x){
    return ...;
}

double solve(double L,double R){
    int mid;
    while(L-R>eps){
        mid=(L+R)/2;
        if(f(mid)>0){
            right=mid;
        }
        else{
            left=mid;
        }
    }
    return mid;
}

2.木棒切割问题

现给出N根木棒，长度均已知，现在希望通过切割它们来得到至少k段长度相等的木棒（长度必须是整数），求这些长度相等的木棒最长能有多长？

//计算每段切割的长度为mid时对应的木棒段数k
int calc_num(int L) {
    int num = 0;
    for (int i = 0; i < N; i++) {
        num += len[i] / L;
    }
    return num;
}


//二分区间为[left, right],传入值为[0,n]
//计算k>K的区间。
int solve(int left, int right) {
    int mid;
    while (left + 1 < right) {  //木棒最短为1
        mid = (left + right) / 2;
        if (calc_num(mid) < K) {
            right = mid;
        }
        else {
            left = mid;     //注意修改
        }
    }
    return right;
}

3.快速幂

给定三个正整数a,b,m，求a^b%m

这里当a和b的范围比较小时，就可以直接只用循环来进行计算，但是当a和b的范围很大时，使用循环就很消耗时间了。

在这里就可以使用快速幂的做法，它是基于二分的思想。使用快速幂针对这道题的思路是：

1)如果b是奇数，则a^b = a * a^(b-1)
2)如果b是偶数，则a^b = a^(b/2) * a^(b/2)

所以我们就可以使用递归的方法来求解这道题：

typedef long long LL;
LL binaryPow(LL a,LL b,LL m){
    if(b==0){
        return 1;
    }
    else if(b%2==0){  //当为偶数时
        int mul=binaryPow(a,b/2,m);
        return mul*mul%m;
    }
    else{  //当为奇数时
        return a*binaryPow(a,b-1,m);
    }
}