21xrx.com
2024-09-19 23:55:34 Thursday
登录
文章检索 我的文章 写文章
C++实现二分查找算法
2023-07-05 11:03:43 深夜i     --     --
C++ 二分查找算法 实现

二分查找,也叫折半查找,是一种基于比较的查找算法。在有序的数组中查找指定元素,通过将数组不断地二分,可以快速地定位指定元素的位置。

C++ 是一种支持面向对象编程的高级程序设计语言,也是实现二分查找算法的常用语言。下面将介绍如何使用 C++ 实现二分查找算法。

二分查找算法的原理是:首先确定查找范围的左右边界,然后取中间位置的元素进行比较,若相等,则查找成功,返回元素索引;否则,根据比较结果将查找范围缩小一半,接着重复上述过程,直到查找到目标元素或范围收缩至空。

接下来是二分查找的 C++ 代码实现:


int binary_search(int arr[], int left, int right, int target) {

  while (left <= right) {

    int mid = left + (right - left) / 2;

    if (arr[mid] == target)

      return mid;

    else if (arr[mid] > target)

      right = mid - 1;

    else

      left = mid + 1;

  }

  // 查找失败,返回 -1

  return -1;

}

在上述代码中,`binary_search` 函数接受四个参数:`arr` 表示要查找的有序数组,`left` 和 `right` 分别表示查找范围的左右边界,`target` 表示要查找的目标元素。该函数使用了 while 循环进行迭代,相对于递归的实现方式,更加在实际工程中更实用。

在每次循环时,我们用 `(left + right) / 2` 或 `left + (right - left) / 2` 计算中间位置 `mid`,然后通过 `if-else` 语句判断该位置上的元素是否等于目标元素。若是,则返回该位置的索引;否则,根据大小关系将查找范围缩小一半。

当循环结束时,若仍未找到目标元素,则说明查找失败,返回 `-1` 表示未找到。

通过上述代码实现,我们可以快速地在有序数组中定位元素,达到更快的查找效率。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复