国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > C++ > 正文

C語言數(shù)據(jù)結(jié)構中二分查找遞歸非遞歸實現(xiàn)并分析

2020-05-23 13:48:44
字體:
供稿:網(wǎng)友

C語言數(shù)據(jù)結(jié)構中二分查找遞歸非遞歸實現(xiàn)并分析

前言:

二分查找在有序數(shù)列的查找過程中算法復雜度低,并且效率很高。因此較為受我們追捧。其實二分查找算法,是一個很經(jīng)典的算法。但是呢,又容易寫錯。因為總是考慮不全邊界問題。

用非遞歸簡單分析一下,在編寫過程中,如果編寫的是以下的代碼:

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

那么我們可以簡單分析一下:

C語言,二分查找,遞歸,非遞歸,數(shù)據(jù)結(jié)構中二分查找遞歸非遞歸實現(xiàn)代碼

 

如果是以下這樣的代碼實現(xiàn):

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

那么可以簡單分析一下為:

C語言,二分查找,遞歸,非遞歸,數(shù)據(jù)結(jié)構中二分查找遞歸非遞歸實現(xiàn)代碼

同樣,遞歸實現(xiàn)的條件也分為兩種,我就只演示一種,代碼如下:

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

感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

 

發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 满城县| 廊坊市| 大港区| 睢宁县| 康乐县| 益阳市| 电白县| 乐亭县| 云和县| 正镶白旗| 长沙县| 昭平县| 达孜县| 隆回县| 南木林县| 本溪市| 松潘县| 上思县| 奉化市| 陵川县| 西昌市| 江西省| 泸州市| 忻州市| 湖北省| 峨眉山市| 淳安县| 浠水县| 县级市| 裕民县| 伊宁县| 大英县| 万年县| 西昌市| 惠州市| 同心县| 镇平县| 巴楚县| 怀仁县| 滦南县| 格尔木市|