文档介绍：******@hit
二分查找算法
1
简单定义:在一个单调有序的集合中查找元素,每次将集合分为左右两部分,判断解在哪个部分中并调整集合上下界,重复直到找到目标元素。
时间复杂度:O (logn),优于直接顺序查找O(n)
二分查找算法
2
例子:
3
//x:待查找的元素, n:数组集合大小, num数组单调递增
int low=0,high=n,mid,res = -1; //low:集合下界 high:集合上节
while(low<=high)
{
mid=(low+high)/2; //mid:将集合分割为两部分
if(num[mid]==x) //查找到符合元素x
{
res = mid;
break;
}
else if(num[mid]<x) //x在右边部分,调整集合下界
low=mid+1;
else //x在左边部分,调整集合上界
high=mid-1;
} //若未找到x,则res = -1
参考程序
4
查找连续函数的写法
//x:待查找的值,Caculate():所要查找的函数,在这里单调递增
//需保证查找的值在区间范围内
double low=“区间下界”,high=“区间上界”,mid;
while(high - low > -6)
{
mid = (high + low)/2;
if(Caculate(mid)<x)
low=mid;
else
high=mid;
}
5
常见拓展
对于某些问题,如果答案具有特定的范围,并且验证答案是否成立的函数具有单调性。则可以在范围内对答案进行二分验证,从而快速确定答案。
6
例子:HOJ2651 PIE
题目大意:有f+1个人分n块披萨,每个人要求分得的面积一样,且披萨只能被切开而不能重新组合,求每个人能分到的最大面积v。
分析:对于每个确定的v,可以计算出最多能满足的人数p。因此得到一个单调递减的函数关系,并且v的范围也可以确定为0~max(size(i)),i=1...n。
7
x轴——每个人分到的面积v
y轴——对应可分最大人数p
对于第一组样例——
图中红点所对应的v值即
为最优解,二分查找满足
p>=4时v的最大值即可得
到答案
8
//由于精度差问题,考虑先将面积 *1000000转化为整数来二分
long long res,mid;
while (low <= high)
{
mid = (high + low) / 2;
if (judge(mid) )
{
low = mid + 1;
res = mid; //最后结果为res
}
else
{
high = mid - 1;
}
}
核心代码
bool judge(long long mid)
{
long long p = 0;
for (int i = 0; i < n; ++i)
{
p += size[i] / mid;
}
return p >= f;
}
9
二分的思想在很多领域中都得到了广泛的应用,是很多算法的基础。相信不难理解整个二分查找的框架和用法。
总结
10