C++ 中二分查找递归非递归实现并分析
在 C++ 编程中，二分查找是一种常用的查找算法，通过将数组分为两部分，并逐步缩小查找范围来找到目标元素。今天我们将介绍 C++ 中二分查找的递归和非递归实现，并对其进行分析。
二分查找的原理
二分查找的原理是将数组分为两部分，並且每次查找都将数组分为两部分，直到找到目标元素为止。假设我们有一个有序数组 arr，并且要查找元素 x，那么我们可以将数组分为两部分：左半部分和右半部分。如果 x 小于中间元素，那么我们可以继续在左半部分查找；如果 x 大于中间元素，那么我们可以继续在右半部分查找。如此重复直到找到目标元素为止。
非递归实现
下面是 C++ 中二分查找的非递归实现：
```cpp
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;
}
```
在上面的代码中，我们使用了 while 循环来实现二分查找。我们首先将数组的起始索引和结束索引分别设置为 0 和 n-1，然后进入循环。在每次循环中，我们计算中间索引 mid，並且比较 x 和 arr[mid] 的大小。如果 x 小于 arr[mid]，那么我们将右半部分的索引设置为 mid-1，否则我们将左半部分的索引设置为 mid+1。如此重复直到找到目标元素为止。
递归实现
下面是 C++ 中二分查找的递归实现：
```cpp
int binaty_search_recursive(int* arr, size_t n, int x, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (x < arr[mid]) {
return binaty_search_recursive(arr, n, x, left, mid - 1);
} else if (x > arr[mid]) {
return binaty_search_recursive(arr, n, x, mid + 1, right);
} else {
return mid;
}
}
int main() {
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << binaty_search_recursive(arr, sizeof(arr) / sizeof(int), 0, 0, sizeof(arr) / sizeof(int) - 1) << endl;
cout << binaty_search_recursive(arr, sizeof(arr) / sizeof(int), 1, 0, sizeof(arr) / sizeof(int) - 1) << endl;
cout << binaty_search_recursive(arr, sizeof(arr) / sizeof(int), 2, 0, sizeof(arr) / sizeof(int) - 1) << endl;
// ...
return 0;
}
```
在上面的代码中，我们使用了递归函数来实现二分查找。我们首先将数组的起始索引和结束索引分别设置为 0 和 n-1，然后调用递归函数。在每次递归调用中，我们计算中间索引 mid，並且比较 x 和 arr[mid] 的大小。如果 x 小于 arr[mid]，那么我们将右半部分的索引设置为 mid-1，否则我们将左半部分的索引设置为 mid+1。如此重复直到找到目标元素为止。
时间复杂度分析
二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。因为在每次循环中，我们将数组的长度缩小了一半，所以时间复杂度为 O(log n)。
结论
二分查找是一种常用的查找算法，通过将数组分为两部分，并逐步缩小查找范围来找到目标元素。C++ 中二分查找的非递归和递归实现都可以使用，而非递归实现更为常用。同时，我们需要注意边界问题，以避免错误的结果。
