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

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

2023-07-05 04:42:52 深夜i -- --

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

二分查找算法是一种高效的查找算法，也是程序员必备的基本算法之一。C++语言提供了很好的支持来实现这种算法，并可以通过计算比较次数来评估算法的效率。

二分查找算法的基本思想是：将有序数组等分成两个部分，如果要查找的元素比中间元素小，那么只需要在左半部分继续查找；如果要查找的元素比中间元素大，那么只需要在右半部分继续查找。这个过程不断缩小查找范围，直到找到要查找的元素或者确定要查找的元素不存在为止。

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


int binarySearch(int arr[], int n, int target) {
  int left = 0, right = n - 1;
  int count = 0; // 计数器，记录比较次数
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
      count++; // 计数器加1，记录当前比较次数
      std::cout << "比较了 " << count << " 次" << std::endl;
      return mid;
    }
    else if (arr[mid] < target) {
      count++; // 计数器加1，记录当前比较次数
      left = mid + 1;
    }
    else {
      count++; // 计数器加1，记录当前比较次数
      right = mid - 1;
    }
  }
  std::cout << "比较了 " << count << " 次" << std::endl;
  return -1; // 没有找到目标元素
}

在上述代码中，我们先定义了`left`和`right`两个指针，分别指向数组的第一个元素和最后一个元素。然后，在`while`循环内部，我们计算了中间元素的下标`mid`，并判断了中间元素和目标元素的大小关系，通过调整`left`和`right`指针来缩小查找范围。最后，如果找到了目标元素，则返回其下标；否则返回-1表示没有找到目标元素。同时，我们还记录了每次比较的次数，并输出到控制台上，方便对算法效率进行评估。

下面我们来看如何计算比较次数。由于二分查找算法的查找次数是`(log2n)+1`，因此，我们只需要在每次比较完后将计数器加1，最终计数器的值就是比较次数。在上述代码中，我们在比较时加上了计数器的更新，而在函数结束时，我们输出计数器的值。

综上，我们可以通过C++语言实现二分查找算法，并可计算出比较次数，从而对算法效率进行评估。这一算法在实际应用中非常广泛，在处理有序数组查找的时候可以显著提高查找速度。

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

下一篇: VC++6.0能否使用中文文件名？

评论区

()

相似文章