C++语言实现二分查找算法，并计算比较次数 |21xrx.com

C++语言实现二分查找算法，并计算比较次数

2023-07-12 21:54:19 深夜i -- --

C++ 二分查找算法比较次数

二分查找算法是一种常见的算法，也叫做折半查找算法。这种算法的基本思想是在有序的序列中，通过每次将数据范围减半来查找目标值。在计算比较次数的时候，每次比较都会将数据操作一次，最终的比较次数取决于数据长度和目标值是否存在。

C++是一种高效的编程语言，在实现二分查找算法时也有很大的帮助。代码如下：


#include <iostream>
using namespace std;
int binarySearch(int arr[], int low, int high, int target, int& compCount)
{
  if(low > high)
    return -1;
  int mid = low + (high - low) / 2;
  if(arr[mid] == target)
    return mid;
  else if(arr[mid] > target)
  {
    compCount++;
    high = mid - 1;
    return binarySearch(arr, low, high, target, compCount);
  }
  else
  {
    compCount++;
    low = mid + 1;
    return binarySearch(arr, low, high, target, compCount);
  }
}
int main()
{
  int arr[] = 14;
  int low = 0;
  int high = sizeof(arr) / sizeof(arr[0]) - 1;
  int target = 11;
  int compCount = 1;
  int result = binarySearch(arr, low, high, target, compCount);
  if(result == -1)
    cout << "未找到指定数字！" << endl;
  else
    cout << "指定数字位于第 " << result + 1 << " 个位置。" << endl;
  cout << "比较次数为：" << compCount << endl;
  return 0;
}

通过上述的代码，我们就可以实现对数组中的数据进行二分查找，并且得到比较次数。在运行示例的过程中，我们可以得到如下的输出结果：

指定数字位于第 4 个位置。

比较次数为：3

从输出结果来看，我们实现的二分查找算法比较高效，比较次数较少。这样的算法应用范围较广，用来查找指定数据的效率明显高于一般的搜索算法。同时，在实现中可以利用C++的高效性，使得二分查找变得更加简单易懂。

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

下一篇: Java数据库读取工具包

评论区

()

相似文章