C++编程实现二分查找算法 |21xrx.com

C++编程实现二分查找算法

2023-06-24 04:00:23 深夜i -- --

C++ 二分查找算法数据结构查找

二分查找算法是一种基于比较的搜索算法，也被称为折半查找。该算法通过将查找区间逐步缩小，直到找到目标元素或者确定目标元素不存在。

在C++中，我们可以用如下的代码实现二分查找算法：


int binarySearch(int arr[], int x, int n)
{
  int left = 0, right = n - 1;
  while (left <= right)
  {
    int mid = left + (right - left) / 2;
    if (arr[mid] == x)
      return mid;
    if (arr[mid] < x)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return -1;
}

上述代码中，arr[]表示数组，x表示要查找的目标元素，n表示数组的大小。left和right分别表示查找区间的左右端点。在while循环中，我们每次将查找区间缩小一半，并根据中间元素与目标元素的大小关系确定下一次查找区间的左右端点。

如果中间元素等于目标元素，则返回中间元素的下标；如果中间元素小于目标元素，则目标元素必然在右侧区间，左端点更新为mid+1；如果中间元素大于目标元素，则目标元素必然在左侧区间，右端点更新为mid-1。

如果最终查找不到目标元素，返回-1。

在实际应用中，二分查找算法可以用于搜索有序数组中的某个元素，也可以用于找到满足某种条件的最大或最小元素。例如，在一个递增（或者递减）的整数数组中，查找第一个大于等于目标元素的位置，可以通过二分查找算法实现。这种情况下，我们需要根据目标元素的大小关系和中间元素的大小关系确定下一次查找区间的左右端点。当区间缩小到只有一个元素时，该元素就是第一个大于等于目标元素的位置。

总之，在编写C++程序时，二分查找算法可以极大地提高搜索效率，增加程序的运行速度。因此，如果我们需要在有序数组中查找元素，就可以考虑使用该算法来实现。

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

下一篇: 如何在vc++6.0中恢复错误提示窗口？

评论区

()

相似文章