1 二分的特点

  • 确定一个区间，使得目标值一定在区间内。
  • 找到一个性质，使其满足：性质有二段性（一边满足性质，一边不满足性质）、答案是二段性的分界点。

    2 二分模板

    2.1 整数二分

    整数二分一般有两种情况，一种是查找满足条件的数的下界位置，称为lower_bound，另一种是求满足条件的数的上界位置，称为upper_bound。

    2.1.1 查找满足条件的数的下界位置

    1. int n;//元素总个数
    2. int num[LENGTH];
    3. int search_lower_bound(int sea_n)
    4. {
    5.   int l=0,r=n-1;
    6.   int mid;
    7.   while(l<r)
    8.   {
    9.       mid=(l+r)/2;
    10.       if(num[mid]>=sea_n)//符合条件
    11.           r=mid;
    12.       else
    13.           l=mid+1;
    14.   }//while结束时l=r
    15.   if(num[l]==sea_n)
    16.       return l;//找到了
    17.   else
    18.       return -1;//没找到
    19. }

    2.1.2 查找满足条件的数的上界位置

    1. int n;//元素总个数
    2. int num[LENGTH];
    3. int search_upper_bound(int sea_n)
    4. {
    5.   int l=0,r=n-1;
    6.   int mid;
    7.   while(l<r)
    8.   {
    9.       mid=(L+r+1)/2;//避免死循环，所以加一，从而取上界
    10.       if(num[mid]<=sea_n)//符合条件
    11.           l=mid;
    12.       else
    13.           r=mid-1;
    14.   }//while结束时l=r
    15.   if(num[l]==sea_n)
    16.       return l;//找到了
    17.   else
    18.       return -1;//没找到
    19. }

    2.2 实数二分

    1. double binary_search_ss(double n)
    2. {
    3.   double l=-10000,r=10000;
    4.   double mid;
    5.   while((r-l)>1e-6)//要比要求的精度小两个数量级
    6.   {
    7.       mid=(l+r)/2;
    8.       if(猜大了)
    9.           r=mid;
    10.       else
    11.           l=mid;
    12.   }
    13.   return mid;
    14. }