作者：sex丶帆布鞋 | 来源：互联网 | 2021-12-12 15:56
C++ 中二分查找递归非递归实现并分析
二分查找在有序数列的查找过程中算法复杂度低，并且效率很高。因此较为受我们追捧。其实二分查找算法，是一个很经典的算法。但是呢，又容易写错。因为总是考虑不全边界问题。
用非递归简单分析一下，在编写过程中，如果编写的是以下的代码：
#include
#include
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])
{
left = mid+1;
}
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout <
那么我们可以简单分析一下：
如果是以下这样的代码实现：
#include
#include
using namespace std;
int binaty_search(int* arr, size_t n, int x)
{
assert(arr);
int left = 0;
int right = n;
while (left 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 <
那么可以简单分析一下为：
同样，递归实现的条件也分为两种，我就只演示一种，代码如下：
#include
#include
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 + 1, right);
}
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout <
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
京公网安备 11010802041100号