算法介绍

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

原理分析

一、精确查找：
每次取中点元素进行比较（把序列分成左右两个部分），如果相等即查找结束（如果有多个相同结果的，可能要求输出最小或是最大的值，需另做处理）；否则如果太大，那说明结果在左边序列里面，在左边继续查找；如果太小，那说明结果在右边序列里面，在右边继续查找；如果中点不存在，即查找失败（结束）。

二、模糊查找：
每次取中点元素进行比较（把序列分成左右两个部分），如果相等即查找结束（如果有多个相同结果的，可能要求输出最小或是最大的值，需另做处理）；否则如果太大，那说明结果在左边序列里面，在左边继续查找；如果太小，那说明结果在右边序列里面，在右边继续查找；如果中点不存在，即查找结束，输出左右两个中最接近的一个。
比如：NOI 01：查找最接近的元素
代码实例：

#include <iostream>
#include <cmath>
using namespace std;
int find(int d[],int x,int l,int r){
int m;
if(l==r) return d[l];
if(r-l==1){
return abs(d[l]-x)<=abs(d[r]-x)?d[l]:d[r];
}
m=(r+l)/2;
if(x==d[m]){
return d[m];
}else if(x>d[m]){
return find(d,x,m,r);
}else{
return find(d,x,l,m);
}
}
int main()
{
int n,m,d[100001],x;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>d[i];
}
cin>>m;
for(int i=0;i<m;i++){
cin>>x;
cout<<find(d,x,0,n-1)<<endl;
}
return 0;
}

三、查找最优解：
先确定解的最小和最大值，然后每次取中点去检查，看是否通过，直到中点不存在，输出结果。
比如：NOI 04:网线主管（切网线）
先确定一个最小值（肯定可以）和一个最大值（肯定不可以），那么结果一定在最小值和最大值之间，再采用二分查找不断取中点测试，如果可以，说明结果有可能更大（在右边），否则说明结果应该更小（在左边），当中点不存在的时候，查找结束，那么左边的值就是最优解。
代码实例：

#include <iostream>
#include <cmath>
using namespace std;

int N,K;
int wx[10001];

int cut(int n)
{
int x=0,y;
for(int i=0;i<N;i++)
{
y=wx[i]/n;
if(y>=1) x+=y;
if(x>=K) break;
}
return x;
}

int findx(int min,int max)
{
if(max-min<=1) return min;
int mid=(min+max)/2;
int x=cut(mid);
if(x>=K) return findx(mid,max);
if(x<K) return findx(min,mid);
}

int main()
{
int max=0,min=0;
float w;
cin>>N>>K;
for(int i=0;i<N;i++)
{
cin>>w;
wx[i]=w*100;
max=wx[i]>max?wx[i]:max;
min=wx[i]<min?wx[i]:min;
}
min=min/(K/N+1);
if(cut(max)>=K) w=max/100.0;
else{
int y=findx(min,max);
w=y/100.0;
}
printf("%.2f",w);
return 0;
}