【C++】二分算法

简介

二分查找又叫折半查找，他是有序线性表的一种查找算法。

算法思想
假定升序排列，下标从 0 0 0开始，二分查找函数如下，返回查找到的下标，查找失败返回 − 1 -1 −1。

int bin_find(int *num,int len,int key){
    int low,high,mid;
    low=0;//查找下界
    high=len-1;//查找上界
    while(low<=high){
		mid=(low+high)/2;//折半
		if(keynum[mid])
			low=mid+1;
		else
			return mid;
	}
	return -1;//查找失败
}

例题查找大于等于

题目描述

给定一个含有 n n n个元素的升序序列和 q q q次询问，每次询问一个数，输出序列中第一个大于等于该数的元素的位置，如果序列中没有符合条件的数，则输出"Not Found"（不输出引号）。

输入格式

第1 1 1 1行输入 2 2 2个整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1le nle 10^5) n(1≤n≤105)和 q ( 1 ≤ q ≤ 1 0 5 ) q(1le qle 10^5) q(1≤q≤105)，表示序列长度和询问次数;

第 2 2 2行输入 n n n个用空格隔开的整数 A i ( 0 ≤ A i ≤ 1 0 9 ) A_i(0le A_ile 10^9) Ai(0≤Ai≤109)，表示这个序列;

接下来输入 q q q行，每行输入 1 1 1个整数，表示要询问的数;

输出格式

对于每组数据中的每次询问，输出一行：如果序列中第一个大于等于该数的元素存在，则输出其位置，否则输出"Not Found"（不包括引号）。

样例输入

样例输出

1 
3 
5 
Not Found

题解

标准的二分查找变形即可，下标从 1 1 1开始，注意可能有重复，查找到合适下标后需要前移到第一次出现的下标。

#include 
using namespace std;
int bin_find(int *num,int len,int key){
    int low,high,mid;
    low=1;//查找下界
    high=len;//查找上界
    while(low<=high){
		mid=(low+high)/2;//折半
		if(keynum[mid])
			low=mid+1;
		else
			break;
	}
	while(mid<=len&&num[mid]1&&num[mid-1]==num[mid]) mid--;//取等,下标左移 
	return mid;
}
int main(){
	int n,q,num[100001],x;
	cin>>n>>q;//输入长度和询问次数
	for(int i=1;i<=n;i++) cin>>num[i]; 
	while(q--){
		cin>>x;//输入查询的x
		int idx=bin_find(num,n,x);
		if(idx!=n+1) cout< 
数的范围 
题目描述 
给定一个按照升序排列的长度为
    
     
      
       
        n
       
      
      
       n
      
     
    n的整数数组，以及
    
     
      
       
        q
       
      
      
       q
      
     
    q个查询。 
对于每个查询，返回一个元素
    
     
      
       
        k
       
      
      
       k
      
     
    k的起始位置和终止位置（位置从
    
     
      
       
        0
       
      
      
       0
      
     
    0开始计数）。 
如果数组中不存在该元素，则返回
    
     
      
       
        −
       
       
        1
       
       
         
       
       
        −
       
       
        1
       
      
      
       -1 -1
      
     
    −1 −1。 
输入格式 
第一行包含整数
    
     
      
       
        n
       
      
      
       n
      
     
    n和
    
     
      
       
        q
       
      
      
       q
      
     
    q，表示数组长度和询问个数。 
第二行包含
    
     
      
       
        n
       
      
      
       n
      
     
    n个整数（均在
    
     
      
       
        1
       
       
        ∼
       
       
        10000
       
      
      
       1sim 10000
      
     
    1∼10000范围内），表示完整数组。 
接下来
    
     
      
       
        q
       
      
      
       q
      
     
    q行，每行包含一个整数k，表示一个询问元素。 
输出格式 
共
    
     
      
       
        q
       
      
      
       q
      
     
    q行，每行包含两个整数，表示所求元素的起始位置和终止位置。 
如果数组中不存在该元素，则返回
    
     
      
       
        −
       
       
        1
       
       
         
       
       
        −
       
       
        1
       
      
      
       -1 -1
      
     
    −1 −1。 
输入样例 
6 3
1 2 2 3 3 4
3
4
5
 
输出样例 
3 4
5 5
-1 -1
 
数据范围与提示 

     
      
       
        
         1
        
        
         ≤
        
        
         n
        
        
         ≤
        
        
         100000
        
        
        
         1
        
        
         ≤
        
        
         q
        
        
         ≤
        
        
         10000
        
        
        
         1
        
        
         ≤
        
        
         k
        
        
         ≤
        
        
         10000
        
       
       
         1le nle 100000\ 1le qle 10000\ 1le kle 10000 
       
      
     1≤n≤1000001≤q≤100001≤k≤10000 
题解 
标准的二分查找修改，找到下标后进行左移右移。 
#include 
using namespace std;
int s,e;//左右下标 
void bin_find(int *num,int len,int key){
    int low,high,mid;
    low=0;//查找下界
    high=len-1;//查找上界
    while(low<=high){
		mid=(low+high)/2;//折半
		if(keynum[mid])
			low=mid+1;
		else{
			s=e=mid;
			break;
		}
	}
	if(num[mid]!=key){//查找失败 
		s=e=-1;
		return;
	}
	while(s>0&&num[s-1]==key) s--;//找左边界 
	while(e>n>>q;//输入长度和询问次数
	for(int i=0;i>num[i]; 
	while(q--){
		cin>>x;//输入查询的x
		bin_find(num,n,x);
		cout< 
数的三次方根 
题目描述 
给定一个浮点数
    
     
      
       
        n
       
      
      
       n
      
     
    n，求它的三次方根。 
输入格式
 共一行，包含一个浮点数
    
     
      
       
        n
       
      
      
       n
      
     
    n。 
输出格式
 共一行，包含一个浮点数，表示问题的解。 
注意，结果保留
    
     
      
       
        6
       
      
      
       6
      
     
    6位小数。 
输入样例 
1000.00
 
输出样例 
10.000000
 
数据范围与提示
 
     
      
       
        
         −
        
        
         10000
        
        
         ≤
        
        
         n
        
        
         ≤
        
        
         10000
        
       
       
         -10000le nle 10000 
       
      
     −10000≤n≤10000 
题解 
采用二分法进行数据逼近，需要注意根可能是负数。 
#include 
#include 
using namespace std;
double solve(double value){
	double low=0,high=value,mid;
	while(fabs(high)-fabs(low)>=1e-7){//精度到达10^(-7)时停止
		mid=(low+high)/2;
		if(abs(mid*mid*mid)>abs(value)){//mid大于三次方根 
			high=mid;
		}else{//mid小于等于三次方根 
			low=mid;
		}
	}
	return mid;
}
int main(){
	double value;
	cin>>value;
	printf("%.6lf",solve(value));//6位小数 
	return 0;
}
 
##　砍树 
题目描述 
伐木工人米尔科需要砍倒
    
     
      
       
        M
       
      
      
       M
      
     
    M米长的木材。这是一个对米尔科来说很容易的工作，因为他有一个漂亮的新伐木机，可以像野火一样砍倒森林。不过，米尔科只被允许砍倒单行树木。 
米尔科的伐木机工作过程如下：米尔科设置一个高度参数
    
     
      
       
        H
       
      
      
       H
      
     
    H（米），伐木机升起一个巨大的锯片到高度
    
     
      
       
        H
       
      
      
       H
      
     
    H，并锯掉所有的树比
    
     
      
       
        H
       
      
      
       H
      
     
    H高的部分（当然，树木不高于
    
     
      
       
        H
       
      
      
       H
      
     
    H米的部分保持不变）。米尔科就行到树木被锯下的部分。 
例如，如果一行树的高度分别为
    
     
      
       
        20
       
      
      
       20
      
     
    20，
    
     
      
       
        15
       
      
      
       15
      
     
    15，
    
     
      
       
        10
       
      
      
       10
      
     
    10和
    
     
      
       
        17
       
      
      
       17
      
     
    17，米尔科把锯片升到
    
     
      
       
        15
       
      
      
       15
      
     
    15米的高度，切割后树木剩下的高度将是
    
     
      
       
        15
       
      
      
       15
      
     
    15，
    
     
      
       
        15
       
      
      
       15
      
     
    15，
    
     
      
       
        10
       
      
      
       10
      
     
    10和
    
     
      
       
        15
       
      
      
       15
      
     
    15，而米尔科将从第
    
     
      
       
        1
       
      
      
       1
      
     
    1棵树得到
    
     
      
       
        5
       
      
      
       5
      
     
    5米，从第
    
     
      
       
        4
       
      
      
       4
      
     
    4棵树得到
    
     
      
       
        2
       
      
      
       2
      
     
    2米，共得到
    
     
      
       
        7
       
      
      
       7
      
     
    7米木材。 
米尔科非常关注生态保护，所以他不会砍掉过多的木材。这正是他为什么尽可能高地设定伐木机锯片的原因。帮助米尔科找到伐木机锯片的最大的整数高度
    
     
      
       
        H
       
      
      
       H
      
     
    H，使得他能得到木材至少为
    
     
      
       
        M
       
      
      
       M
      
     
    M米。换句话说，如果再升高
    
     
      
       
        1
       
      
      
       1
      
     
    1米，则他将得不到
    
     
      
       
        M
       
      
      
       M
      
     
    M米木材。 
输入格式 
第
    
     
      
       
        1
       
      
      
       1
      
     
    1行：
    
     
      
       
        2
       
      
      
       2
      
     
    2个整数
    
     
      
       
        N
       
      
      
       N
      
     
    N和
    
     
      
       
        M
       
      
      
       M
      
     
    M，
    
     
      
       
        N
       
      
      
       N
      
     
    N表示树木的数量（
    
     
      
       
        1
       
       
        ≤
       
       
        N
       
       
        ≤
       
       
        1000000
       
      
      
       1le Nle 1000000
      
     
    1≤N≤1000000）,
    
     
      
       
        M
       
      
      
       M
      
     
    M表示需要的木材总长度（
    
     
      
       
        1
       
       
        ≤
       
       
        M
       
       
        ≤
       
       
        2000000000
       
      
      
       1le Mle 2000000000
      
     
    1≤M≤2000000000） 
第
    
     
      
       
        2
       
      
      
       2
      
     
    2行：
    
     
      
       
        N
       
      
      
       N
      
     
    N个整数表示每棵树的高度，值均不超过
    
     
      
       
        1000000000
       
      
      
       1000000000
      
     
    1000000000。所有木材长度之和大于
    
     
      
       
        M
       
      
      
       M
      
     
    M，因此必有解。 
输出格式 
第
    
     
      
       
        1
       
      
      
       1
      
     
    1行：
    
     
      
       
        1
       
      
      
       1
      
     
    1个整数，表示砍树的最高高度。 
样例输入 
5 20
4 42 40 26 46
 
样例输出 
36
 
题解 
假设函数
    
     
      
       
        f
       
       
        (
       
       
        h
       
       
        )
       
      
      
       f(h)
      
     
    f(h)是砍树后得到的木材总长度，则f(h)单调递减，可以采用二分法求得临界值
    
     
      
       
        H
       
      
      
       H
      
     
    H使得
    
     
      
       
        f
       
       
        (
       
       
        H
       
       
        )
       
       
        >
       
       
        =
       
       
        M
       
      
      
       f(H)>=M
      
     
    f(H)>=M且
    
     
      
       
        f
       
       
        (
       
       
        H
       
       
        +
       
       
        1
       
       
        )
       
       
        <
       
       
        M
       
      
      
       f(H+1) 
#include 
using namespace std;
typedef long long ll;
ll tree[1000000];
int n,m;//n棵树,需要m米 
ll f(ll h){
	ll sum=0;
	for(int i=0;ih){//取等差值为0,省略等于 
			sum+=tree[i]-h;
		}
	}
	return sum;
}
int main(){
	ll low=1,high=1,mid;//查找边界 
	cin>>n>>m;
	for(int i=0;i>tree[i];//输入 
		if(tree[i]>high) high=tree[i];//记录最大高度 
	}
	while(low=m) low=mid;//保证low能用 
		else high=mid-1;//high减小 
	}
	cout< 
进击的奶牛 
题目描述 
Farmer John 建造了一个有
    
     
      
       
        N
       
       
        (
       
       
        2
       
       
        ≤
       
       
        N
       
       
        ≤
       
       
        100
       
       
        ,
       
       
        000
       
       
        )
       
      
      
       N(2le Nle 100,000)
      
     
    N(2≤N≤100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是
    
     
      
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         x
        
        
         N
        
       
       
        (
       
       
        0
       
       
        ≤
       
       
        
         x
        
        
         i
        
       
       
        ≤
       
       
        1
       
       
        ,
       
       
        000
       
       
        ,
       
       
        000
       
       
        ,
       
       
        000
       
       
        )
       
      
      
       x_1,dots ,x_N(0le x_ile 1,000,000,000)
      
     
    x1,…,xN(0≤xi≤1,000,000,000)。 
他的
    
     
      
       
        C
       
       
        (
       
       
        2
       
       
        ≤
       
       
        C
       
       
        ≤
       
       
        N
       
       
        )
       
      
      
       C(2le Cle N)
      
     
    C(2≤C≤N)头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？ 
输入格式 
第
    
     
      
       
        1
       
      
      
       1
      
     
    1行：两个用空格隔开的数字
    
     
      
       
        N
       
      
      
       N
      
     
    N和
    
     
      
       
        C
       
      
      
       C
      
     
    C。 
第
    
     
      
       
        2
       
       
        ∼
       
       
        N
       
       
        +
       
       
        1
       
      
      
       2sim N+1
      
     
    2∼N+1行：每行一个整数，表示每个隔间的坐标。 
输出格式 
输出只有一行，即相邻两头牛最大的最近距离。 
样例输入 
5 3
1 
2 
8 
4 
9 
 
样例输出 
3
 
题解
 以隔间距离为搜索值进行二分查找，搜索是否存在
    
     
      
       
        C
       
      
      
       C
      
     
    C个隔间满足该距离。 
#include 
#include 
#define N (int)1e5
using namespace std;
typedef long long ll;
int check(int x[],int n,int c,int mid){//计算是否有c个隔间满足 
	int cnt=1,pre=x[0];//cnt是隔间数,至少是1,pre是上一个隔间坐标 
	for(int i=1;i=mid){//坐标距离满足 
			cnt++;
			pre=x[i];
		}
		if(cnt==c) return 1;//满足返回1 
	}
	return 0;//不满足返回0 
}
int main(){
	int n,c,low,high,mid;
	int x[N];
	cin>>n>>c;
	for(int i=0;i>x[i];
	}
	sort(x,x+n);//坐标排序 
	low=0,high=x[n-1]-x[0];//隔间最小距离和最大距离 
	while(low 
一元三次方程求解 
题目描述 
有形如：
    
     
      
       
        a
       
       
        
         x
        
        
         3
        
       
       
        +
       
       
        b
       
       
        
         x
        
        
         2
        
       
       
        +
       
       
        c
       
       
        x
       
       
        +
       
       
        d
       
       
        =
       
       
        0
       
      
      
       ax^3+bx^2+cx+d=0
      
     
    ax3+bx2+cx+d=0这样的一个一元三次方程。 
给出该方程中各项的系数(
    
     
      
       
        a
       
      
      
       a
      
     
    a，
    
     
      
       
        b
       
      
      
       b
      
     
    b，
    
     
      
       
        c
       
      
      
       c
      
     
    c，
    
     
      
       
        d
       
      
      
       d
      
     
    d均为实数)，并约定该方程存在三个不同实根(根的范围在
    
     
      
       
        −
       
       
        100
       
      
      
       -100
      
     
    −100至
    
     
      
       
        100
       
      
      
       100
      
     
    100之间)，且根与根之差的绝对值
    
     
      
       
        >
       
       
        =
       
       
        1
       
      
      
       >=1
      
     
    >=1。 
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后
    
     
      
       
        2
       
      
      
       2
      
     
    2位。 
提示：记方程
    
     
      
       
        f
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        0
       
      
      
       f(x)=0
      
     
    f(x)=0，若存在
    
     
      
       
        2
       
      
      
       2
      
     
    2个数
    
     
      
       
        x
       
       
        1
       
      
      
       x1
      
     
    x1和
    
     
      
       
        x
       
       
        2
       
      
      
       x2
      
     
    x2，且
    
     
      
       
        x
       
       
        1
       
       
        <
       
       
        x
       
       
        2
       
      
      
       x1 
输入格式 
一行，
    
     
      
       
        4
       
      
      
       4
      
     
    4个实数
    
     
      
       
        A
       
       
        ,
       
       
        B
       
       
        ,
       
       
        C
       
       
        ,
       
       
        D
       
      
      
       A,B,C,D
      
     
    A,B,C,D 
输出格式 
一行，
    
     
      
       
        3
       
      
      
       3
      
     
    3个实根，并精确到小数点后
    
     
      
       
        2
       
      
      
       2
      
     
    2位。 
样例输入 
1 -5 -4 20
 
样例输出 
-2.00 2.00 5.00
 
题解 
题目规定根在
    
     
      
       
        [
       
       
        −
       
       
        100
       
       
        ,
       
       
        100
       
       
        ]
       
      
      
       [-100,100]
      
     
    [−100,100]之间且根绝对值之差
    
     
      
       
        ≥
       
       
        1
       
      
      
       ge 1
      
     
    ≥1，则可以在
    
     
      
       
        [
       
       
        −
       
       
        99
       
       
        ,
       
       
        100
       
       
        ]
       
      
      
       [-99,100]
      
     
    [−99,100]中循环整数，不取
    
     
      
       
        −
       
       
        100
       
      
      
       -100
      
     
    −100是因为方便计算
    
     
      
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ,
       
       
        i
       
       
        ]
       
      
      
       [i-1,i]
      
     
    [i−1,i]区间，对每一个长度为
    
     
      
       
        1
       
      
      
       1
      
     
    1的小区间进行二分法求根，根据零点定理
    
     
      
       
        f
       
       
        (
       
       
        i
       
       
        −
       
       
        1
       
       
        )
       
       
        ∗
       
       
        f
       
       
        (
       
       
        i
       
       
        )
       
       
        ≤
       
       
        0
       
      
      
       f(i-1)*f(i)le0
      
     
    f(i−1)∗f(i)≤0判定区间是否有根。 
#include 
using namespace std;
typedef long long ll;
double a,b,c,d;
double f(double x){
	return a*x*x*x+b*x*x+c*x+d;//三次函数 
}
double bin_search(double low,double high){
	double mid;
	while(high-low>1e-3){
		mid=(low+high)/2;
		if(f(mid)*f(low)<0){//low~mid之间 
			high=mid;
		}else if(f(mid)*f(high)<0){
			low=mid;
		}else{
			return mid;
		}
	}
	return mid;
}
int main(){
	cin>>a>>b>>c>>d;
	for(double i=-99;i<=100;i++){
		if(f(i-1)==0){//i是一个根 
			printf("%.2lf ",i-1);
			continue;
		}
		if(f(i-1)*f(i)<0){//有根
			printf("%.2lf ",bin_search(i-1,i));
		}
	}
	return 0;
}
 
版权声明 
本文档归cout0所有，仅供学习使用，未经允许，不得转载。

【C++】二分算法

C/C++/C#相关栏目本月热门文章