如何分析中二分查找递归与非递归实现的差异？

本文共计1349个文字，预计阅读时间需要6分钟。

C++ 中实现二分查找递归与非递归版本，并分析其在有序序列中的查找过程及算法复杂度。二分查找算法复杂度低，效率高，是我们追求的目标。

二分查找是一种经典的查找算法，适用于有序序列。其基本思想是：每次将待查找区间分成两半，判断目标值位于哪一半，然后继续在那一半中查找，直到找到目标值或区间为空。

递归实现

cppint binarySearchRecursive(int arr[], int left, int right, int target) { if (right >=left) { int mid=left + (right - left) / 2; if (arr[mid]==target) return mid; if (arr[mid] > target) return binarySearchRecursive(arr, left, mid - 1, target); return binarySearchRecursive(arr, mid + 1, right, target); } return -1;}

非递归实现

cppint binarySearchIterative(int arr[], int left, int right, int target) { while (left target) right=mid - 1; else left=mid + 1; } return -1;}

分析

二分查找算法在有序序列中的查找过程如下：

1. 计算中间位置 `mid`。

2.判断中间位置的值是否为目标值。

3.如果是目标值，返回索引；如果不是，根据目标值与中间位置值的大小关系，缩小查找范围。

二分查找算法的时间复杂度为 O(log n)，空间复杂度为 O(1)。这是因为每次查找都将查找范围缩小一半，所以查找次数与 log n 成正比。

二分查找算法效率高，适用于大量数据的查找。

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

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