C++ 中二分查找遞歸非遞歸實現並分析。本站提示廣大學習愛好者:(C++ 中二分查找遞歸非遞歸實現並分析)文章只能為提供參考,不一定能成為您想要的結果。以下是C++ 中二分查找遞歸非遞歸實現並分析正文
投稿:lqh
這篇文章主要介紹了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; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!