【算法】二分查找(整数二分和浮点数二分)

这篇具有很好参考价值的文章主要介绍了【算法】二分查找(整数二分和浮点数二分)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

大家好!今天我们来学习二分查找算法,这是一种效率很高的算法哦!

目录

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. 整数二分

整数二分过程:

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

 普遍规律:

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

 我们发现:

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

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

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

#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;
}

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

3.2 Acwing789. 数的范围

原题链接:https://www.acwing.com/problem/content/791/

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

#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));
	}
}

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

4. 浮点数二分

我们看下图:

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

分析:

(其实是个二分答案的题目)

y=x^3,我们知道这是个单调递增的函数。

-10000开三次方根大概是-27,10000开三次方根大概是27。

因为-10000<=y<=10000,我们为了方便,把左边界设置成-100,右边界设置成100。

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

 我们可以直观看到-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/

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

#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;
}

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

6.2 洛谷 P1024 [NOIP2001 提高组] 一元三次方程求解

原题链接:https://www.luogu.com.cn/problem/P1024

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

 思路分析:

因为有三个不同实根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)时,我们要想知道根的确切位置,就可以进行二分(因为根是实数,所以我们采用浮点数二分

二分,设区间中间位置为midmid=(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;
}

【算法】二分查找(整数二分和浮点数二分),算法,算法,二分,二分查找,折半查找,整数二分,浮点数二分,c++

7. 总结

二分查找体现了“分治”的思想,又是二分答案的基础,效率又非常高(O(logN)),所以我们学好这个算法很有必要哦!文章来源地址https://www.toymoban.com/news/detail-687128.html

到了这里,关于【算法】二分查找(整数二分和浮点数二分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二分查找--查找整数位置

    描述 二分查找 又叫 折半查找。它采用的是\\\"分治策略\\\"。 给出非降序排列的 n 个整数,查找是否存在某个整数,如果存在,则输出其位置。 输入描述 第一行是一个整数 n(0n≤200000) 表示整数的个数。 接下来是 n 个整数,每个整数之间用一个空格分隔。 接下来一行是一个

    2024年02月13日
    浏览(43)
  • 折半查找算法(BinarySearch)

            查找算法是一种在数字列表中确定目标元素所在位置的算法。假设给定一个目标元素 11 和一个包含元素 11 的数字列表(例如 10, 11, 12,13,14, 15, 16, 17, 18, 19, 20),然后在该数字列表中找到目标元素的位置。         折半查找算法也叫做对分查找和二分查找。折半

    2024年02月03日
    浏览(42)
  • C语言折半查找算法及代码实现

    1.折半查找的定义: 在计算机中, 折半查找 ,也称 二分搜索。它 是一种在有序数组中查找某一特定元素的搜索算法。 2.折半查找的实现原理:                  搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素

    2024年02月05日
    浏览(59)
  • 头歌(C语言)-数据结构与算法-查找-第1关:实现折半查找

    任务描述 相关知识 编程要求 测试说明 任务描述 本关要求通过补全函数 BSL_FindKey 来实现在已排序的顺序表中查找关键码值为 key 的结点并返回该结点的编号。 相关知识 折半查找通常是针对顺序存储的线性表,线性表的结点按关键码从小到大排序,后面称之为折半查找的顺序

    2024年02月10日
    浏览(63)
  • 【算法系列篇】二分查找——这还是你所知道的二分查找算法吗?

    在生活中,我们往往会遇到在数组中查找某个确定的元素的时候,通常我们会选择使用暴力解法,这样虽然简单,但是时间复杂度是O(N),时间效率比较低。那么是否有方法可以使得在具有二段性的数组中找某一特定的元素的时间复杂度低于0(N)呢?答案是肯定的,当我们可以

    2024年02月11日
    浏览(51)
  • 【算法系列 | 8】深入解析查找算法之—二分查找

    心若有阳光,你便会看见这个世界有那么多美好值得期待和向往。 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力,成为更好的自己! 今天第8讲,讲一下查找算法的二分查找 查找算法是很常见的一类问题,主

    2024年02月07日
    浏览(55)
  • C++二分算法(二分查找&二分答案)细节详解

     二分算法可以分为 二分查找 和 二分答案 。 以在一个 升序数组 中查找一个数为例。它每次考察数组当前部分的 中间元素 ,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果

    2024年02月08日
    浏览(52)
  • 【Python查找算法】二分查找、线性查找、哈希查找

    目录 1 二分查找算法  2 线性查找算法 3 哈希查找算法         二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素或确定目标元素不存在。 以下是二分查找的

    2024年02月08日
    浏览(51)
  • 【算法】简单的二分查找算法

    一个简单的二分查找算法:         简单描述:算法由静态方法rank()实现,它接受一个整数键和一个有序的int数组作为参数,如果整数存在于数组,返回它的索引,否则返回-1,算法使用两个变量lo和hi,并保证整数如果存在于数组中则它一定存在于a[lo...hi]中,然后通过循

    2024年01月21日
    浏览(57)
  • 【算法小课堂】二分查找算法

    当我们要从一个序列中查找一个元素的时候,最快想到的方法就是顺序查找法(即:从前到后依次查找)。但这种方法过于无脑,就是暴力的把每个元素都排查一遍。元素个数少的时候还行,一旦元素个数多起来,效率是非常低下,所以在实际中这种查找的方法是被摒弃的。

    2024年02月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包