C++ 中二分查找递归非递归实现并分析
作者:lqh 发布时间:2023-06-19 06:51:31
标签:C++,二分查找,递归
C++ 中二分查找递归非递归实现并分析
二分查找在有序数列的查找过程中算法复杂度低,并且效率很高。因此较为受我们追捧。其实二分查找算法,是一个很经典的算法。但是呢,又容易写错。因为总是考虑不全边界问题。
用非递归简单分析一下,在编写过程中,如果编写的是以下的代码:
#include<iostream>
#include<assert.h>
using namespace std;
int binaty_search(int* arr, size_t n, int x)
{
assert(arr);
int left = 0;
int right = n - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (x < arr[mid])
{
right = mid-1;
}
else if (x > arr[mid])
{
left = mid+1;
}
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 0) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 1) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 2) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 3) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 4) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 5) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 6) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 7) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 8) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 9) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 10) << endl;
return 0;
}
那么我们可以简单分析一下:
如果是以下这样的代码实现:
#include<iostream>
#include<assert.h>
using namespace std;
int binaty_search(int* arr, size_t n, int x)
{
assert(arr);
int left = 0;
int right = n;
while (left < right)
{
int mid = (left + right) / 2;
if (x < arr[mid])
{
right = mid;
}
else if (x > arr[mid])
{
left = mid + 1;
}
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 0) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 1) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 2) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 3) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 4) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 5) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 6) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 7) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 8) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 9) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 10) << endl;
return 0;
}
那么可以简单分析一下为:
同样,递归实现的条件也分为两种,我就只演示一种,代码如下:
#include<iostream>
#include<assert.h>
using namespace std;
int binaty_srarch(int* arr, int x, int left, int right)
{
assert(arr);
int mid;
if (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] == x)
{
return mid;
}
else
if (x < arr[mid])
{
return binaty_srarch(arr, x, left, right - 1);
}
else if (x>arr[mid])
{
return binaty_srarch(arr, x, left + 1, right);
}
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << binaty_srarch(arr, 0, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 1, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 2, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 3, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 4, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 5, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 6, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 7, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 8, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 9, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 10, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
return 0;
}
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
来源:http://blog.csdn.net/he_shuai20/article/details/56855670
0
投稿
猜你喜欢
- 写在前面:今天用保存QQ账号和密码的实战演练,带大家掌握Android存储中最基本的文件存储方式文件存储是Android中最基本的一种数据存
- 利用栈实现一个简易计算器(Java实现),供大家参考,具体内容如下一、思路分析当我们输入一个类似于“7*2+100-5+
- 本文实例为大家分享了C++实现俄罗斯方块的具体代码,供大家参考,具体内容如下先是效果图:主菜单:游戏:设置:错误处理:代码:#include
- ObjectMapper 忽略字段大小写核心代码:ObjectMapper mapper = new ObjectMapper();mapp
- 解决办法:1.VCS--->Enable Version Control Integration2.选择要关联的版本工具补充:git
- 以下摘自胖哥分享的 2022开工福利教程。在学习Spring Security的时候你有没有下面这两个疑问:Spring Security的
- Activity中Toast的使用Toast.makeText(this,"ADD",Toast.LENGTH_SHOR
- 打jar包实现分离依赖lib和配置为了业务需要配置文件和jar分离,便于使用者修改配置信息,在网上找了很久,最终找到一个简单有效的方法。操作
- 开发缘由:公司需要调用天眼查-开放平台 ,验证客户的的营业执照信息是否在存续期,并将企业基本信息返回,之后和使用百度图文识别的企业信息进行对
- spring mvc @PathVariable / 带斜杠方式获取遇上这个问题,百度google了一下,抄袭里面的内容,可以实现,在此备忘
- WebSocket介绍WebSocket是HTML5开始提供的一种在单个 TCP 连接上进行全双工通讯的协议。在WebSocket API中
- Bezier曲线的形状是通过一组多边折线(特征多边形)的各顶点唯一地定义出来的。在这组顶点中:(1)只有第一个顶点和最后一个顶点在曲线上;(
- 最近JAVA和JSwing上手练习了一下贪吃蛇,供大家参考,具体内容如下欢迎交流和加入新的内容用到了JSwing,下面是一些具体的思路实现&
- 下载地址在这里:http://dotnetzip.codeplex.com/下载到的包里有很多个dll文件,一般引用Ionic.Zip.dl
- Dialog和Toast所有人肯定都不会陌生的,这个我们平时用的实在是太多了。而Snackbar是Design Support库中提供的新控
- Rsa加密RSA是目前最有影响力的公钥加密算法,RSA也是第一个既能用于数据加密也能用于数字签名的算法。该算法基于一个十分简单的数论事实:将
- springmvc下载中文文件名称为下划线springboot项目中,在下载文件的时候,通过封装ResponseEntity,将文件流写入b
- 这几天Java项目中需要用到Redis,于是学习了一下使用Jedis来操作Redis服务器的相关知识,下面为具体的配置和代码。1、Maven
- 生产者和消费者问题是线程模型中的经典问题:生产者和消费者在同一时间段内共用同一个存储空间,如下图所示,生产者向空间里存放数据,而消费者取用数
- 本文实例为大家分享了Android实现指针刻度转盘的具体代码,供大家参考,具体内容如下一. 先上个效果图,实现如图所示刻度转盘和2个文本的绘