二分查找：二分查找是基于有序序列的查找算法，该算法一开始令[lift,rigth]为整个序列的下标区间，然后每次测试当前[lift,rigth]的中间位置mid=(lift+rigth)/2,判断mid与预查询的元素x的大小。

二分查找的高效之处在于，每一步都可以去除当前区间中的一半元素，因此其时间复杂度是O(logn)。 

二分做题模板：

例题1：

789.数的范围
给定一个按照升序排列的长度为n的整数数组,以吸q个查询。对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。如果数组中不存在该元素,则返回  -1 -1 。
输入格式
第一行包含整数n和q,示数组长度和询问个数。
第二行包含n个整数(均在1 ~ 10000范围内),表示完整数组。
接下来q行，每行包含一个整数 k,表示一个询问元素。
输出格式
共q行,行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1 。
数据范围
1≤n≤100000
1 < q≤10000
1 <k< 10000
输入样例:
6 3
1 2 2 3 3 4

3
4

5

输出样例:
3 4
5 5
-1 -1

#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#include<queue>
#include<string>       
#include<iostream>
#include<cstring>
#include<map>
#include<stack>
#include<set>
using namespace std;
const int N = 100010;
int n, q;
int a[N];
int main()
{
    cin>>n>>q;
    for(int i=0;i<n;i++) 
    {
    	cin>>a[i];//遍历数组； 
	}
	while (q--)// q次查询； 
	{
		int x;
		cin>>x;//x就是我们在数组中要找的数 
		int l=0,r=n-1; 
		while(l<r) 
		{
			int mid=l+r>>1; //首先要找到>=x的第一个数，这样我们就可以找到第一个数的下标 
			if(a[mid]>=x)//当a[mid]>= x时，说明mid及其左边可能含有值为x的元素
			{
				r=mid;//所以将mid赋值给r，缩小一半范围 
			}
			else
			{
				l=mid+1;//否则，就是a[mid]<x,mid在其右侧，所以就将mid+1赋值给l,因为mid<x,所以mid本身不符合，所以mid+1; 
			}
		}
		if(a[l]==x)//如果l和r相遇之后，a[l]是等于x的，那么就输出该数下标； 
		{
			cout<<l<<" ";
			l=0,r=n-1;
			while(l<r)
			{
				int mid=l+r+1>>1;
				if(a[mid]<x+1)// 开始寻找<x+1的数，也就是x的最后一个位置； 
				{
					l=mid;//就说明x+1在mid的右侧，所以将mid赋值给l; 
				}
				else
				{
					r=mid-1;//否则x+1就在mid的左侧，因为mid<x+1,mid本身不符合，所以mid-1; 
				}
			}
			cout<<r<<endl;//输出r; 
		}
		else//如果l和r相遇后的数a[l]！=x,那么就输出-1 -1； 
		{
			cout<<"-1 -1"<<endl;
		}
	}
    return 0; 
} 

例题2：

 题目 1885: 

蓝桥杯2017年第八届真题-分巧克力

题目描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一.共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这N块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:
1.形状是正方形，边长是整数
2.大小相同
例如一.块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。.
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么?
输入
第一行包含两个整数N和K。(1 <= N, K <=100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
65
56
样例输出
2
 

#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include<cstring>
#include<map>
#include<stack>
#include<set>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],w[N];
bool check(int x)//x就是我们要找的最大的边长； 
{
	int num=0;//我们可以截取的块数； 
	for(int i=0;i<n;i++)
	{
		num=num+(h[i]/x)*(w[i]/x);//(h[i]/x)*(w[i]/x)表示的是我们可以截取的块数； 
	} 
	if(num>=m)//如果截取的块数大于小朋友的人数； 
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>h[i]>>w[i];//长和宽； 
	}
	int l=1,r=1e5;//l=1是因为输入保证每位小朋友至少能获得一块1x1的巧克力
	while(l<r)//套用模板，取得是右侧，向下取整； 
	{
		int mid=l+r+1>>1;
		if(check(mid))
		{
			l=mid;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<l;//最后当l和r相遇时，就输出l或r; 
	return 0;
 } 

如果理解有误，请不吝赐教。谢谢！