大家好!今天我们来学习二分查找算法,这是一种效率很高的算法哦!
目录
1. 整数二分
2. 整数二分模板
3. 整数二分模板题
3.1 洛谷 P2249 【深基13.例1】查找
3.2 Acwing789. 数的范围
4. 浮点数二分
5. 浮点数二分模板
6. 浮点数二分模板题
6.1 Acwing 790.数的三次方根
6.2 洛谷 P1024 [NOIP2001 提高组] 一元三次方程求解
7. 总结
二分查找也称折半查找(Binary Search),是一种效率较高的查找方法,时间复杂度为O(logN)。
(不清楚怎么算时间复杂度的小伙伴可以看看这篇文章哦~https://blog.csdn.net/m0_62531913/article/details/132019833?spm=1001.2014.3001.5502)
二分查找采用了“分治”策略。使用二分查找时,数组中的元素之间得有单调性(升序或者降序)。
二分的模板据我目前所知有三个,但是下面是我个人认为最好的一种(比较简单,不容易写错~)
1. 整数二分
整数二分过程:
普遍规律:
我们发现:
2. 整数二分模板
查找最后一个<=x的数的下标:
int find(int x)
{
int l = 0, r = n + 1; //开区间
while (l + 1 < r) //l+1==r时结束
{
int mid = (l + r) >> 1; //相当于mid=(l+r)/2;
if (a[mid] <= x) l = mid;
else r = mid;
}
return l;
}
查找第一个>=x的数的下标:
int find(int x)
{
int l = 0, r = n + 1; //开区间
while (l + 1 < r) //l+1==r时结束
{
int mid = (l + r) >> 1; //相当于mid=(l+r)/2;
if (a[mid] >= x) r = mid;
else l = mid;
}
return r;
}
3. 整数二分模板题
3.1 洛谷 P2249 【深基13.例1】查找
原题链接:https://www.luogu.com.cn/problem/P2249
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], n, m;
int find(int x)
{
int l = 0, r = n + 1;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (a[mid] >= x) r = mid;
else l = mid;
}
if (a[r] == x) return r;
else return -1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
while (m--)
{
int k;
scanf("%d", &k);
printf("%d ", find(k));
}
return 0;
}
3.2 Acwing789. 数的范围
原题链接:https://www.acwing.com/problem/content/791/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, q;
int find1(int x)
{
int l = -1, r = n;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (a[mid] >= x) r = mid;
else l = mid;
}
if (a[r] == x) return r;
else return -1;
}
int find2(int x)
{
int l = -1, r = n;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (a[mid] <= x) l = mid;
else r = mid;
}
if (a[l] == x) return l;
else return -1;
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (q--)
{
int k;
scanf("%d", &k);
printf("%d %d\n", find1(k), find2(k));
}
}
4. 浮点数二分
我们看下图:
分析:
(其实是个二分答案的题目)
y=x^3,我们知道这是个单调递增的函数。
-10000开三次方根大概是-27,10000开三次方根大概是27。
因为-10000<=y<=10000,我们为了方便,把左边界设置成-100,右边界设置成100。
我们可以直观看到-27~27包含在-100~100。所以这样设置左右边界是没有问题滴。
我们不断二分缩小范围,当l和r非常接近时(r-l<=1e-8),我们就认为找到了这个三次方根。
否则我们用while(r-l>=1e-8)继续循环遍历。
又因为是递增的,所以mid*mid*mid<=y,我们让区间往右靠(l=mid);反之,当mid*mid*mid>y时,我们让区间往左靠(r=mid)。
最后返回左边界l即可。(其实这里返回左边界l和右边界r都可以,因为它们非常非常非常接近)
5. 浮点数二分模板
double find(double y)
{
double l = -100, r = 100;
while (r - l > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid <= y) l = mid;
else r = mid;
}
return l;
}
6. 浮点数二分模板题
6.1 Acwing 790.数的三次方根
原题链接:https://www.acwing.com/problem/content/792/
#include<bits/stdc++.h>
using namespace std;
double n;
int main()
{
scanf("%lf", &n);
double l = -100, r = 100;
while (r - l > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid <= n) l = mid;
else r = mid;
}
printf("%.6lf\n", l);
return 0;
}
6.2 洛谷 P1024 [NOIP2001 提高组] 一元三次方程求解
原题链接:https://www.luogu.com.cn/problem/P1024
思路分析:
因为有三个不同实根x,且根x的区间为-100到100,根与根之差的绝对值>=1。
我们就可以从根x的区间[-100,100]进行枚举,我们将搜索区间定为[l,r],而r=l+1。
根据题目提示(即零点定理),我们知道:
(1)若f(l)==0,l为方程的根。
(2)若f(l)*f(r)<0,则根在区间[l,r]内。
(3)若f(l)*f(r)>0,则根不在区间[l,r]内。设定[r,r+1]为下一搜索区间。
当遇到情况(2)时,我们要想知道根的确切位置,就可以进行二分(因为根是实数,所以我们采用浮点数二分)
二分,设区间中间位置为mid,mid=(l+r)/2。将区间[l,r]分为左右两个区间,左子区间[l,mid]和右子区间[mid,r]。
若f(l)*f(mid)<0(根在左子区间),我们调整右端点继续二分(r=mid)。
若f(mid)*f(r)<0(根在右子区间),我们调整左端点继续二分(l=mid)。
一直到找到根时停止循环,此时l就是方程的根。(因为精度足够,所以这里也可以让r作为方程的根)
#include<bits/stdc++.h>
using namespace std;
double a, b, c, d;
double f(double x)
{
return a * x * x * x + b * x * x + c * x + d;
}
int main()
{
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
for (double i = -100; i <= 100; i++) //枚举每一个可能的根
{
double l = i, r = i + 1;
if (f(l) == 0) printf("%.2lf ", i); //左端点是根,直接输出
if (f(l) * f(r) < 0) //根在区间[l,r]中
{
while (r - l > 1e-4) //浮点数二分
{
double mid = (l + r) / 2; //计算区间[l,r]的中间位置
if (f(l) * f(mid) < 0) r = mid; //若根在左子区间,则调整右端点
else l = mid; //若根在右子区间,则调整左端点
}
printf("%.2lf ", l);
}
}
return 0;
}
文章来源:https://www.toymoban.com/news/detail-687128.html
7. 总结
二分查找体现了“分治”的思想,又是二分答案的基础,效率又非常高(O(logN)),所以我们学好这个算法很有必要哦!文章来源地址https://www.toymoban.com/news/detail-687128.html
到了这里,关于【算法】二分查找(整数二分和浮点数二分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!