二分查找（二分搜索）所有情况及模板简单总结以及lower_bound函数

青旅半醒 2022-12-13 14:19 177阅读 0赞

### 文章目录 ###

*   *  二分搜索
     *   *   *  1、从有序数组中查找某值
             *  2、二分答案
             *  3、最大化最小值
             *  4、最大化平均值
     *  c++中的二分函数 -- lower\_bound和upper\_bound函数

## 二分搜索 ##

二分就是不断缩小解空间的范围，从而求得问题的最优解。二分不光可以用在查找某值的位置，也可以用二分搜索法找问题的答案。下面是用二分的各种情况。

#### 1、从有序数组中查找某值 ####

这是最基本的二分搜索法，若在一个有序数组里找一个数，最朴素的算法就是从头到尾一个一个的找，如此的时间复杂度是O(n)，当n很大时找一遍复杂度就很高。此时我们可以利用他的有序性这个特点，我们可以直接从中点查找，若中点的数比查找的数小，我们在右半边接着按照这个方法查找，若中点的数比查找的数大，我们接着在左半边查找，若相等则刚好找到，这时时间复杂度降为O(logn)。

**代码模板**

int n,x,a[N];
    
    int solve(int x)
    { 
    	int l = -1,r = n;	//左右端点初始值
    	while(r-l > 1)		//满足mid存在
    	{ 
    		int mid = (r+l) / 2;	//中点
    		if(a[mid] > x)	//往左半边找
    			r = mid;
    		else if(a[mid] < x)	//往右半边找
    			l = mid;
    		else		//正好找到就退出循环
    			break;
    	}
    	return (r+l) / 2;	//返回位置
    }

#### 2、二分答案 ####

有些题我们知道答案的区间范围，并且可以判断我们尝试的结果和答案的大小，这时我们就可以用二分很快的找答案。我们可以不断地尝试每一个中点的数，用一个函数判断该数是不是所求的答案。若不是，我们再在左半边或者右半边找。尝试答案的复杂度仅为O(logn)。

**经典例题与代码模板**

**例题：** 有n条绳子，长度分别为ai，我们要从这n条绳子中切出k条长度相同的小绳子，求这k条绳子最长有多长（精确到两位小数）。（poj1064）

**思路：** 我们可以知道k条绳子最长是这n条绳子中最长的那根，最小是0，所以我们就在这个区间内二分答案，并且我们需要一个判断函数，判断该答案能不能切出k条相同长度的绳子，若成立，则在右半边找更大的答案；若不成立，说明太长了，应该往左半边找可成立的答案。直到解的范围足够小为止。  
**代码：**

int n,k;
    double line[N],maxn;
    
    bool judge(double x)	//判断函数
    { 
    	int sum = 0;
    	for(int i = 0;i < n;i++)
    		sum += (int)(line[i] / x);	//计算总共能剪出多少根长度为x的绳子
    	return sum >= k;	//若总数大于等于k说明成立
    }
    
    void solve()
    { 
    	double l = 0,r = maxn;
    	for(int i = 0;i < 100;i++)	//重复二分，直到解的范围足够小，二分100次的范围已经很小了
    	{ 
    		double mid = (r+l) / 2;	//计算中点
    		if(judge(mid))		//如果判断mid成立
    			l = mid;	//往右半边找更大的答案
    		else
    			r = mid;	//不成立往左半边找可成立的答案
    	}
    	printf("%.2lf\n",l);
    }

#### 3、最大化最小值 ####

类似的最大化最小值或者最小化最大值都可以用二分搜索法很好地解决

**例题：** 现在有n间牛舍，排在一条线上，第i间在xi的位置。但是他的m头牛对牛舍不满意，为防止他们之间相互攻击，需要将每头牛放在离其他牛尽可能远的地方。也就是要最大化最近的两头牛之间的距离。（poj2456）

**思路：** 二分最小间距实现最大化，二分间距，若间距成立，就在右半边找；若不成立，就在左半边找一个更小的间距使得在此最小间距下能放下所有牛。  
**代码：**

int n,m,x[N];
    
    bool judge(int d)
    { 
    	int last = 0;
    	for(int i = 1;i < m;i++)
    	{ 
    		int cur = last + 1;
    		while(cur < n && x[cur] - x[last] < d)
    			cur++;
    		if(cur == n)
    			return 0;
    		last = cur;
    	}
    	return 1;
    }
    
    void solve()
    { 
    	sort(x,x+n);
    	int l = 0,r = maxn;
    	while(r-l > 1)
    	{ 
    		int mid = (r+l) / 2;
    		if(judge(mid))
    			l = mid;
    		else
    			r = mid;
    	}
    	cout << l << endl;
    }

#### 4、最大化平均值 ####

和最大化最小值思路差不多

**例题：** 有n个物品的重量和价值分别是wi和vi。从中选出k个物品使得单位重量的价值最大。

**思路：** 这是一道很经典的最大化平均值的题，我们一般最先想到的方法可能是把物品按单位价值进行排序，然后从大到小贪心的取k个物品，但是会发现这样是错的，举个例子：n = 3，k = 2，（w，v） = \{（2，2）,（5，3）,（2，1）\}，贪心得到的答案是5/7 = 0.714，但是取第一件和第三件物品得到的答案是3/4 = 0.75 。所以贪心的方法是不可行的，那么该如何解决呢？

我们可以用二分搜索法来计算这个问题，我们二分一下可能的单位价值记为x。思考这个问题，假设我们选取的k个物品是集合s，那么他们的单位价值最小就是  
 ∑ i = 1 k v i ∑ i = 1 k w i ≥ X \\frac\{\\sum\_\{i=1\}^kv\_i\}\{\\sum\_\{i=1\}^kw\_i\}\\ge X ∑i=1kwi∑i=1kvi≥X  
将不等式变形就得到了  
 ∑ i = 1 k ( v i − x × w i ) ≥ 0 \\sum\_\{i=1\}^k(v\_i-x\\times w\_i)\\ge 0 i=1∑k(vi−x×wi)≥0  
因此可以对（ v i − x × w i v\_i-x\\times w\_i vi−x×wi）的值从大到小排序贪心的取前k个的和，判断和是否大于等于0即可。

**代码：**

int n,k,w[N],v[N];
    double y[N];
    bool judge(double x)
    { 
    	for(int i = 0;i < n;i++)
    		y[i] = v[i] - x * w[i];
    	sort(y,y+n);
    	reverse(y,y+n);
    	double sum = 0;
    	for(int i = 0;i < k;i++)
    		sum += y[i];
    	return sum >= 0;
    }
    
    void solve()
    { 
    	double l = 0,r = INF;
    	for(int i = 0;i < 100;i++)
    	{ 
    		double mid = (r+l) / 2;
    		if(judge(mid))
    			l = mid;
    		else
    			r = mid;
    	}
    	cout << l << endl;
    }

--------------------

## c++中的二分函数 – lower\_bound和upper\_bound函数 ##

> 1、lower\_bound(begin,end,num);  
> 2、upper\_bound(begin,end,num);

lower\_bound()和upper\_bound()都是利用二分查找的方法在一个排好序的数组中进行查找的。他们都在algorithm头文件中。

**①lower\_bound(begin,end,num)** 是从数组中的begin（地址）位置到end-1（地址）位置二分查找第一个大于等于num的数字，若找到返回值是其地址，否则返回值是end。通过返回的地址减去起始地址begin，得到数字在数组中的下标。  
**②upper\_bound(begin,end,num)** 是从数组中的begin（地址）位置到end-1（地址）位置二分查找第一个大于num的数字，返回值同上。  
**③lower\_bound(begin,end,num,greater< type>())** 是从数组中的begin（地址）位置到end-1（地址）位置二分查找第一个小于等于num的数字，返回值同上。  
**④upper\_bound(begin,end,num,greater< type>())** 是从数组中的begin（地址）位置到end-1（地址）位置二分查找第一个小于num的数字，返回值同上。

#include<iostream>
    #include<algorithm>
    
    using namespace std;
    
    int main()
    { 
    	int a[5] = { 1,2,3,4,5};
    	cout << lower_bound(a,a+5,2)-a << endl;
    	cout << upper_bound(a,a+5,3)-a << endl;
    	cout << lower_bound(a,a+5,99)-a << endl;
    	int b[5] = { 2,5,8,9,11};
    	cout << lower_bound(b,b+5,5,greater<int>())-b << endl;
    	cout << upper_bound(b,b+5,9,greater<int>())-b << endl;
    
    	return 0;
    }

二分还可以用在很多地方，最重要的是要将题目转化为一个二分模型，再去计算。