C++ 中二分查找递归非递归实现并分析
作者:lqh 时间:2023-06-19 06:51:31
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
标签:C++,二分查找,递归
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Android 验证码功能实现代码
2023-06-12 23:19:06
![](https://img.aspxhome.com/file/2023/0/138620_0s.gif)
C# 通过NI-VISA操作Tektronix TBS 2000B系列示波器的实现步骤
2023-11-02 01:44:38
![](https://img.aspxhome.com/file/2023/0/84460_0s.png)
详解Java图形化编程中的鼠标事件设计
2022-07-11 08:11:31
Unity快速生成常用文件夹的方法
2023-12-11 20:37:43
![](https://img.aspxhome.com/file/2023/1/83241_0s.jpg)
java实现推箱子小游戏
2023-02-09 04:57:52
![](https://img.aspxhome.com/file/2023/0/99740_0s.png)
C#构造函数详解
2023-02-25 22:38:50
java中set接口使用方法详解
2023-03-15 06:10:12
java中ArrayList和LinkedList的区别详解
2022-09-05 11:13:48
Java的方法和this关键字如何理解与应用
2023-02-14 02:43:29
![](https://img.aspxhome.com/file/2023/7/121947_0s.png)
Java实现链表数据结构的方法
2023-10-19 20:36:57
![](https://img.aspxhome.com/file/2023/1/88191_0s.jpg)
C#中内联函数的用法介绍
2023-04-18 18:29:18
Android自定义ProgressDialog加载图片
2022-07-28 22:08:39
![](https://img.aspxhome.com/file/2023/5/95005_0s.gif)
Android 资源 id详解及的动态获取
2023-06-25 00:32:21
开发工具EesyCode使用方法解析
2023-06-27 13:50:46
![](https://img.aspxhome.com/file/2023/0/84260_0s.png)
详细解读JAVA多线程实现的三种方式
2022-01-14 04:35:31
android使用ItemDecoration给RecyclerView 添加水印
2022-01-17 19:42:54
![](https://img.aspxhome.com/file/2023/6/100616_0s.gif)
Java 如何调用long的最大值和最小值
2021-07-24 02:27:18
![](https://img.aspxhome.com/file/2023/0/60590_0s.jpg)
C#针对xml基本操作及保存配置文件应用实例
2022-11-24 05:51:17
Android仿天猫横向滑动指示器功能的实现
2022-10-09 16:53:58
![](https://img.aspxhome.com/file/2023/2/101822_0s.jpg)
浅析C++字节对齐容易被忽略的两个问题
2022-06-02 20:29:59