之前一直学得不明不白,似懂非懂,如今算是懂了大概。
首先了解二分查找的定义,使用原因,使用要求和目标有助于高效掌握这个算法。
什么是二分查找?
二分查找也称折半查找(Binary Search),又分为整数二分和浮点二分
为什么使用二分查找?
效率比线性查找高。
什么时候可以二分查找?
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。
二分查找查找的是什么?(重要)
在有序区间里找到第一个大于等于目标值的值,
或最后一个大于等于目标值的值
前者寻找左边界(即寻找符合性质的第一个点)
后者寻找右边界(即寻找符合性质的最后一个点)
整型二分模板(注释都有解释)
1.寻找第一个大于等于k的值(左边界点)
int a[44];//为有序数组
int k;//目标值
int bsearch(int l, int r)
{
while(l < r){//最终一定是l=r=mid
int mid = l + r >> 1;//向下取整 当lr贴在一起时,mid取l,下方r和l都有移动缩小区间。这个很重要。a>>1 等于 a/2
if(a[mid] >= k) r = mid; //寻找第一个大于等于k的值
else l = mid + 1;
}
if(a[r] != k) return -1;//寻找第一个大于等于k的值,也就意味着这个值不一定等于k,这点很重要
return l;//return r;
}
2.寻找最后一个个小于等于k的值(右边界点)
nt a[44];//为有序数组
int k;//目标值
int bsearch(int l, int r)
{
while(l < r){//最终一定是l=r=mid
int mid = l + r + 1 >> 1; //需要向上取整,当lr贴在一起时,mid取r,下方r和l都有移动缩小区间。
if(a[mid] <= k) l = mid;//寻找最后一个小于等于k的值
else r = mid - 1;
}
if(a[r] != k) return -1;//寻找最后一个个小于等于k的值,也就意味着这个值不一定等于k,这点很重要
return l;
}
关于模板2中的向上取整原因
可以假设如果向下取整。
int mid = l + r >> 1;//向下取整 那么当lr相邻时,mid = l,这时下方的l = l
if(a[mid] <= k) l = mid;//l = l 意味着 区间无法缩小。那么while循环就会一直进行下去。
else r = mid - 1;//而且r = l-1, ,直接击穿边界。
浮点二分模板
多用于求根,开方,比整型二分简单多了
int main()
{
//求n^1/3
double n;
cin >> n;
double l = -10000, r = 10000, mid;
while(r - l > 1e-8){//只要满足精度就好了
mid = (l + r )/ 2;
if(mid * mid * mid >= n) r = mid;
else l = mid ;
}
printf("%.6f", l);
}