21xrx.com
2024-11-22 03:44:32 Friday
登录
文章检索 我的文章 写文章
C++二分法代码实现
2023-07-11 16:13:17 深夜i     --     --
C++ 二分法 代码 实现 搜索

C++是一门经典的编程语言,被广泛应用于计算机程序设计、数据结构、算法分析和数值计算等诸多领域。其中,二分法也是C++中经典的算法之一。在本文中,我们将介绍C++中二分法的实现方式。

二分法,也称二分查找或折半查找,是一种基于有序数列的查找算法。基本思想是将查找区间不断缩小,直到找到目标值或者没有找到目标值。二分法的时间复杂度为O(logn),比线性查找的O(n)更快。

下面是C++中二分法的基本实现代码:


int binary_search(int array[], int n, int target) {

  int left = 0, right = n - 1;

  while (left <= right) {

    int mid = (left + right) / 2;

    if (array[mid] == target)

      return mid;

     else if (array[mid] < target) {

      left = mid + 1;

    } else

      right = mid - 1;

    

  }

  return -1;

}

这个函数接受三个参数:一个有序数组、数组元素个数和需要查找的目标值,返回值为目标值在数组中的下标。该函数先设定左边界left为0,右边界right为n-1,然后在while循环内不断缩小查找范围。在每次循环中,计算中间位置mid=(left+right)/2,并将目标值与中间位置的元素比较。如果相等,返回mid;如果目标值比中间位置的元素大,将左边界left更新为mid+1;否则,将右边界right更新为mid-1。如果没有查找到目标值,返回-1。

除了基本的二分法查询,还有一些变形,比如查找第一个大于或等于目标值的元素、查找最后一个小于或等于目标值的元素等。下面是查找第一个大于或等于目标值的元素的代码:


int lower_bound(int array[], int n, int target) {

  int left = 0, right = n;

  while (left < right) {

    int mid = (left + right) / 2;

    if (array[mid] < target) {

      left = mid + 1;

    } else

      right = mid;

    

  }

  return left;

}

这个函数返回第一个大于或等于目标值的元素的下标,如果所有元素都小于目标值,则返回n。与基本的二分法查找的区别在于,如果中间位置的元素小于目标值,则将左边界left更新为mid+1;否则,将右边界right更新为mid,因为当前mid可能是第一个大于或等于目标值的元素。

二分法是一种高效的查找算法,可以应用于多种场景,比如查找有序数组或二叉搜索树中的元素等。在C++中,实现二分法只需要短短几行代码,但是需要注意边界条件的处理,防止出现死循环或者数组越界等问题。相信随着对C++的理解和掌握,越来越多的程序员可以使用二分法解决实际问题。

  
  

评论区

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