溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
