C++二分查找算法实现代码 |21xrx.com

C++二分查找算法实现代码

2023-07-01 15:26:21 深夜i -- --

C++ 二分查找算法实现代码

二分查找算法是一种高效的查找方法，也称为折半查找。它的基本思想是将有序数组分成两部分，从中间位置开始查找，如果中间值大于查找值，则在左半边继续查找，反之则在右半边继续查找，直到找到目标值为止。

以下是C++实现二分查找算法的代码：


#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int target)
{
  int left = 0, right = n - 1;
  while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] == target)
      return mid;
    else if (arr[mid] < target)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return -1;
}
int main()
{
  int arr[] = 7;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 3;
  int result = binarySearch(arr, n, target);
  if (result == -1)
    cout << "目标值不在数组中";
  else
    cout << "目标值在数组中的位置是：" << result;
  return 0;
}

首先定义了一个函数binarySearch，它接受三个参数：一个有序数组arr、该数组的长度n和要查找的目标值target。函数中使用了两个变量left和right来记录数组的左右下标，最开始初始化为数组的左右边界。

接着使用while循环不断查找目标值，每次将数组的中间位置mid计算出来，如果中间值等于目标值，则目标值已经找到，返回mid位置。如果中间值小于目标值，则在右半边查找，即将left赋值为mid+1；反之则在左半边查找，即将right赋值为mid-1。如果最终没有找到目标值，则返回-1。

在主函数main中定义了一个有序数组arr和要查找的目标值target，分别使用sizeof和 sizeof(arr[0])来计算数组的长度n。然后调用binarySearch函数来查找目标值，并将结果存储在result变量中。最后根据函数返回值的正负判断目标值是否存在于数组中，并输出结果。

总结

二分查找算法是一种高效的查找方法，它的时间复杂度为O(logn)，适用于对有序数组进行查找。C++提供了标准库函数std::lower_bound和std::upper_bound也可以实现二分查找。在实际应用中，可以根据数据结构的特点和运算效率来选择算法实现。

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

下一篇: "C语言与C++代码示例：解析其区别"

评论区

()

相似文章