C++递归实现二分查找 |21xrx.com

C++递归实现二分查找

2023-07-06 02:50:09 深夜i 20 0

C++ 递归实现二分查找

二分查找是一种高效的查找算法，通过将待查找的数组不断划分成两半来寻找目标元素，时间复杂度为O(log n)。在C++语言中，可以使用递归实现二分查找。

递归是指函数调用自身的技术，类似于一个函数不断地在自己的内部调用自己，直到满足退出条件。对于二分查找，我们可以将待查找数组的左边界、右边界以及目标元素作为递归函数的参数传入。

下面是C++递归实现二分查找的代码：

#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
  if (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
      return mid;
    
    else if (arr[mid] > target) {
      return binarySearch(arr, left, mid - 1, target);
    } else {
      return binarySearch(arr, mid + 1, right, target);
    }
  }
  return -1; // 如果找不到则返回-1
}
int main() {
  int arr[] = 11;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 7;
  int result = binarySearch(arr, 0, n - 1, target);
  (result == -1) ? cout << "Element is not present in array" : cout << "Element is present at index " << result;
  return 0;
}

在上述代码中，我们定义了一个名为binarySearch的递归函数，其参数为数组arr，左边界left，右边界right，目标元素target。如果left <= right，就通过计算中间索引mid，如果找到目标元素，就返回其索引mid，否则根据目标元素与中间元素的大小关系调用二分查找的左半部分或右半部分，直到 left > right 为止（此时说明已经在数组 arr 中搜索完毕但未找到 target）。

在主函数中，我们定义一个数组arr，目标元素target为7，然后调用二分查找的递归函数进行查找。当查找到目标元素时，函数返回其索引，否则返回-1。最后通过三目运算符输出结果。

最后，希望本文可以给读者提供帮助，使读者能够了解C++递归实现二分查找的编写方法和实现原理，从而更加深入了解C++编程语言。

上一篇: idea打包java可执行jar包

下一篇: C++ 多线程调用同一类

评论区

相似文章