C语言数据结构中二分查找递归非递归实现并分析

2020-05-23 13:48:44

字体：大中小

来源：转载

供稿：网友

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

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

上一篇：C++智能指针shared_ptr分析

下一篇：C++算法之在无序数组中选择第k小个数的实现方法