C++ 中二分查找遞歸非遞歸實(shí)現(xiàn)并分析
C++ 中二分查找遞歸非遞歸實(shí)現(xiàn)并分析
二分查找在有序數(shù)列的查找過程中算法復(fù)雜度低,并且效率很高。因此較為受我們追捧。其實(shí)二分查找算法,是一個很經(jīng)典的算法。但是呢,又容易寫錯。因?yà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 - 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; }
那么我們可以簡單分析一下:
如果是以下這樣的代碼實(shí)現(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; }
那么可以簡單分析一下為:
同樣,遞歸實(shí)現(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; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
相關(guān)文章
解析C++中的for循環(huán)以及基于范圍的for語句使用
這篇文章主要介紹了解析C++中的for循環(huán)以及基于范圍的for語句使用,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2016-01-01C++使用循環(huán)計(jì)算標(biāo)準(zhǔn)差的代碼實(shí)現(xiàn)
在C++中,計(jì)算標(biāo)準(zhǔn)差可以使用循環(huán)來實(shí)現(xiàn),本文給大家介紹了一個示例代碼,演示了如何使用循環(huán)計(jì)算標(biāo)準(zhǔn)差,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,需要的朋友可以參考下2023-12-12C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹堆
這篇文章主要為大家介紹了C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹堆的圖文示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-05-05C語言實(shí)現(xiàn)隨機(jī)讀寫文件的函數(shù)詳解
文件的隨機(jī)讀寫,可以在文件中指定的任意位置讀或者寫。這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)隨機(jī)讀寫文件的3個函數(shù),感興趣的可以了解一下2023-03-03