C++实现二分查找算法的主函数 |21xrx.com

C++实现二分查找算法的主函数

2023-06-23 20:16:52 深夜i -- --

C++ 二分查找算法主函数

二分查找算法是计算机科学领域中非常常见的算法之一，它是一种旨在寻找已排序数组中特定元素位置的算法。在这篇文章中，我们将探讨使用C++语言实现二分查找算法的主函数。

在C++编程语言中，二分查找算法要求输入的数组必须按照一定顺序排序，通常以升序排序。接下来的C++代码实现了一个基本的二分查找算法的主函数。


int binarySearch(int arr[], int left, int right, int target) {
  if (left <= right) {
    int mid = left + (right - left) / 2; // 计算中间元素的下标
    if (arr[mid] == target)  // 如果中间元素就是我们要查找的目标
    else if (arr[mid] < target) { // 如果中间元素小于目标，则在右侧继续查找
      return binarySearch(arr, mid + 1, right, target);
    }
    else { // 否则，在左侧继续查找
      return binarySearch(arr, left, mid - 1, target);
    }
  }
  return -1; // 如果没有找到目标，则返回-1
}

在上述代码中，函数的输入参数包括整型数组 arr 、查找区间的左右端点下标 left、right 和目标元素 target 。这个函数返回目标元素在数组中的下标，没有找到则返回-1。

函数使用了递归来确定查找区间范围，并计算中间元素的下标。如果中间元素是要查找的目标，则直接返回；如果中间元素比目标小，则在右边区间内继续查找，否则在左边继续查找。

下面的代码展示了如何使用binarySearch函数：


int main() {
  int arr[] = 9;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 9;
  int result = binarySearch(arr, 0, n - 1, target);
  if (result == -1)
    std::cout << "目标元素不在数组中" << std::endl;
  
  else
    std::cout << "目标元素在数组的第" << result << "个元素位置" << std::endl;
  
  return 0;
}

在上述代码中，我们定义了一个整型数组 arr ，并使用其它变量初始化了查找区间的左右边界。然后我们调用了binarySearch函数，并将函数返回值赋给一个整型变量 result 。如果result的值是-1，则说明目标元素不在数组中，否则我们就可以在输出语句中计算出目标元素在数组中的位置。

总结：

本文深入解析二分查找算法，并通过C++语言实现了该算法的主函数，我们可以使用这个函数在一个已排序数组中找到目标元素位置。二分查找算法的计算复杂度为O(log n)，在已排序数组中查找元素是常见操作之一，因此这个算法非常实用。

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

下一篇: 如何在c++中判断一个函数是否被调用？

评论区

()

相似文章