C++二分查找代码：返回查找次数 |21xrx.com

C++二分查找代码：返回查找次数

2023-06-22 04:32:06 深夜i -- --

C++ 二分查找代码查找次数

在算法中，二分查找（Binary Search）是一种常用的查找算法，它适用于有序的数列。它的查找原理为，将关键字与中间值进行比较，不断缩小查找范围，直到找到关键字或者证明其不存在。

C++语言提供了一个二分查找函数 `std::binary_search()`，可以方便地在一个有序的序列中查找某个特定的元素。这个函数的使用方法非常简单，只需要包含头文件 ` `，就可以在你的程序中使用它了。其函数签名如下：


template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);

其中，`first` 和 `last` 分别表示输入的数组的首地址和末地址，`value` 表示要查找的元素。如果查找成功，函数返回 true，并且查找次数为 $O(\log n)$；如果查找失败，函数返回 false，并且查找次数为 $O(\log n)$。由此可知，在使用二分查找进行查找时，它的平均时间复杂度是 $O(\log n)$，当然，对于较小的数据规模，其优势就不是很明显了。

通常情况下，在二分查找的过程中，我们会统计其中的查找次数，这样可以更好地了解算法的性能。下面是一个基于二分查找实现的 C++ 代码，可以返回查找次数：


#include <iostream>
#include <algorithm>
#include <vector>
int binarySearch(std::vector<int>& arr, int target)
{
  int cnt = 0;
  int left = 0, right = arr.size() - 1;
  while (left <= right)
  {
    int mid = (left + right) / 2;
    if (arr[mid] == target)
    {
      cnt++;
      break;
    }
    else if (arr[mid] < target)
    {
      left = mid + 1;
    }
    else
    
      right = mid - 1;
    
    cnt++;
  }
  return cnt;
}
int main()
{
  std::vector<int> arr = 6;
  int target = 5;  
  int cnt = binarySearch(arr, target);
  std::cout << "查找次数为：" << cnt << std::endl;
}

此代码中，我们定义了一个名为 `binarySearch` 的函数，该函数接受一个数组 `arr` 和要查找的目标 `target`。然后，我们定义了两个指针 `left` 和 `right`，分别指向数组的首地址和末地址。在循环过程中，我们计算了中间位置 `mid` 的索引值，判断中间值是否等于目标值。如果是，则表示查找成功，返回查找次数；否则，我们按照数组有序的性质，确定要查询的子区间，并继续二分搜索。在每次迭代中，我们都会将计数器 `cnt` 的值加一，以记录查找次数。

你可以多次运行代码，看看二分查找在处理不同数据规模时的表现。同时，你还可以尝试修改代码，实现其他常用算法。这有助于您更好地理解算法的本质，熟练地掌握 C++ 语言的基础语法。

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

下一篇: C++中常量合法性的判断方法简介

评论区

()

相似文章