二分查找（折半查找）（内含CodeForces - 1760F ）

在数组中想要找到一个元素，我们最先想到的就是遍历数组，用if语句判断它们是否相等，但时间复杂度太高，我们也不想遍历数组中的每个元素，感觉太麻烦了。这时就可以用二分查找的方法：先将数组排序，然后不断折中数组，只需比较中值与目标值的大小，更新中值的大小就行了，这样可以大大减少时间复杂度。

下面是非递归的二分查找方式：(用了个while循环来不断更新mid的值以及端点值）

int Find(int *a,int n,int v){
	int low=0,high=n-1,mid;
	while(low<=high){
		mid=(low+high)/2;
		if(a[mid]==v) return mid;
		else if(a[mid]<v) low=mid+1;//往右边大的找 
		else high=mid-1;//往左边小的找 
	}
	return -1;
}

下面是递归的二分查找方式：

int Find(int *a,int low,int high,int v){
	if(low>=high) return -1;
	int mid=(low+high)/2;
	if(a[mid]==v) return mid;
	else if(a[mid]<v) return Find(a,mid+1,high,v);
	else return Find(a,low,mid-1,v);
}

注意！这些数组都是有序数组（从小到大），如果数组是无序的，使用二分查找之前时一定要先进行排序。

当然，#include<algorithm>头文件中包含的lower_bound(begin,end,v)函数也可以用于查找（作用：返回大于等于v元素的最小元素的指针）。注意！lower_bound返回的是一个指针，所以还要减去数组首地址。类似的，还有upper_bound函数（作用：返回数组中大于v元素的最小元素的指针）

	int x;
	cin>>x;
	int p=lower_bound(a,a+length,x)-a;
	if(a[p]==x) cout<"found"<<endl;
	else cout<<"no found"<<endl;

那么是只有查找具体元素这种时候才会用到二分查找吗？当然不是！

当题目让你去找一个答案，这个答案满足条件A，让你去求answer的最大最小值，如果没有具体公式，我们求解起来还是非常困难的，如果answer还具有单调性，我们不妨直接用二分查找，测试它是否满足条件，如果满足条件，继续二分，看它是不是最值。

#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
typedef long long ll;
ll s[200005];
ll e[200005];
bool comp(ll a,ll b){
	return a>b;
}//希望得到最小的k,所以需要先做金币多的任务
int main(){
	int t;
	cin>>t;
	while(t--){
		ll n,c,d;
		cin>>n>>c>>d;
		memset(s,0,sizeof(s));
		memset(e,0,sizeof(e));//必须初始化，因为我们用到了空数组，而我们不能让它为空 
		for(int i=1;i<=n;i++){
			cin>>s[i];
		}
		sort(s+1,s+1+n,comp);//排序 
		for(int i=1;i<=max(n,d);i++){
			e[i]=e[i-1]+s[i];
		}
		if(e[min(n,d)]>=c){
			cout<<"Infinity"<<endl;
		}
		else if(s[1]*d<c) cout<<"Impossible"<<endl;//k等于0都没用 
		else{
			ll r=1,l=d-1,k;//k不可能等于d,所以直接用d-1 
			while(r<=l){
				ll mid=(r+l)/2;
				ll x=e[mid]*(d/mid)+e[d%mid];//循环使用s数组 
				if(x>=c){
					k=mid-1;//因为现在索引从1开始 
					r=mid+1;
				}
				else{
					l=mid-1;
				}
			}
			cout<<k<<endl;
		}
		
	}
	return 0; 
}