二分算法略解

算法萌新的学习记录，可能存在错误，纯个人理解。

什么样的数据适合用二分算法？对于学过的同学来说可能会回答数据存在单调性。一般来说，数据存在单调性一定能用二分算法，但能用二分的数据不一定非得是单调的，换句话说就是数据的单调性是能用二分算法的充分不必要条件。

Q：什么是二分算法？

A：二分法(Bisection method)：数学上对于在区间[a,b]上连续不断且满足f(a)*f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在区间二等分，使区间两个端点逐步逼近零点，进而得到零点的近似值的方法。

例如猜数字游戏：给定一个1–100之间的正整数，让你猜。猜的过程中给出大小判断的提醒，问怎么才能快速地猜出来？
最快的方法是：每次猜区间的中间点的数字。如果中间点大于给定数字，下次就猜前半部分的中间点数字；如果中间点数字小于给定数字，下次就猜后半部分的中间点数字。

Q：二分算法能用来干嘛？

A：二分算法可以在一组数据中快速查找某个特定元素的位置或者确定某个条件是否满足。具体来说，如果一组数据中存在着某个性质点能把数据划分，即存在着某种分区规则，使得数据可以被分成两部分，一部分满足某个条件，另一部分不满足该条件，那么就可以使用二分算法来高效地找到这个分区点或者查找目标元素。

整数二分

对于整数二分，我们假设存在一长度为n的数据S，有x∈S使得S被划分为{S[0],....,x}{S[k],....,S[n]}两部分，分别记作数据A，B。那么根据二分算法的性质我们可以找出x或者S[k]在S中的位置。

我们先要知道x能划分S是因为A与B中数据有不同的性质。

先来找S[k]的位置，即B的右端点

/// 设l为区间S的左端点，r为右端点，通过不断调整l，r来找到答案
int l = -1,r = n;
//当l还在r的左边时则说明还没有找到答案，因为答案只有一个
while(l+1!=r){
    int mid = (r+l)/2;// 找到中间位置
    // 判断中间位置的数据是否满足B数据的条件
    if(check(mid)){
        //如果满足，则答案位置肯定在mid的左边或者刚好在mid位置，则更新r=mid
        r = mid;
    }else{
        //如果不满足，则答案肯定在mid的右侧，且不可能在mid处，则更新l=mid
        l=mid;
    }
}
//算法中r不断递减，l不断递增，不断向答案逼近

例1：789. 数的范围 - AcWing题库

#include<iostream>
using namespace std;
const int N=100010;
int n,m,q[N];


void BR(int& l,int& r,int k){
  while(l+1!=r)
        {
            int mid=l+r>>1;
            
            if(q[mid]>=k) r=mid;
            else l=mid;
  }
}

void BL(int& ll,int& rr,int k){
  while(ll+1!=rr)
    {
                    
    int mid=ll+rr>>1;
    if(q[mid]<=k) ll=mid;
    else rr=mid;
  }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>q[i];
    while(m--)
    {
        int k;
        cin>>k;
        int l=-1,r=n;
        BR(l,r,k);
        if(q[r]!=k) printf("-1 -1\n");

        else{
          printf("%d ",r);
               
          int ll=-1,rr=n;
          BL(ll,rr,k);
              if(q[ll]!=k) printf("%d\n",r);
              else printf("%d\n",ll);
        }
    }
}

浮点数二分

浮点数二分相对于整数二分简单一点，相信学会了整数二分不需要过多介绍了

来个题自己感悟一下

790. 数的三次方根 - AcWing题库

#include <bits/stdc++.h>
using namespace std;


int main() { 
    double n;
    cin>>n;
    double l = -10000,r = 10000;
    double epsilon = 0.0000001
    while(r-l>epsilon){
        double mid = (l+r)/2;
        if(mid*mid*mid<n)l = mid;
        else r = mid;
    }
    printf("%.6lf",l);
    return 0;
}

二分算法略解