二分查找又称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。其思想是将查找区间不断分成两半，直到找到目标元素或者查找区间为空。

下面我们就来讲一下在C++中如何实现二分查找，并返回二分查找的次数。

首先，给出C++代码实现二分查找：

int binary_search(int arr[], int left, int right, int target, int &count)
{
  while(left <= right)
  {
    int mid = left + (right - left) / 2;
    count++; // 记录查找次数
    if(arr[mid] == target)  return mid;
    else if(arr[mid] < target) left = mid + 1;
    else  right = mid - 1;
  }
  return -1; // 没有找到目标元素
}

这里使用了迭代循环的方法实现二分查找。arr为已排序的数组，left、right分别为数组的左右端点，target为目标元素。count用于记录查找次数，初始值为0。

在while循环中，每次计算mid的值，如果arr[mid]等于target，则返回mid；如果arr[mid]小于target，则说明目标元素在右半部分，将左端点left指向mid+1；如果arr[mid]大于target，则说明目标元素在左半部分，将右端点right指向mid-1。

如果while循环结束时仍未找到目标元素，则返回-1。

通过上述代码，我们可以看到count被传入函数binary_search中，并在while循环中每次加1，即记录了二分查找的次数。

下面是一个调用示例：

int main()
{
  int arr[] = 3;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 5;
  int count = 0;
  int res = binary_search(arr, 0, n-1, target, count);
  if(res == -1)
  
    cout << "没有找到目标元素" << endl;
  
  else
  
    cout << "目标元素的下标为：" << res << endl;
  
  cout << "二分查找的次数为：" << count << endl;
  return 0;
}

输出如下：

目标元素的下标为：2
二分查找的次数为：2

可以看到，该程序实现了对数组arr中目标元素5的二分查找，并返回查找的次数为2。

总结：

本文介绍了如何在C++中实现二分查找，并返回查找次数。对于大数据量的查找，二分查找是一种高效的算法，值得我们学习和掌握。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政