C++二分法代码实现 |21xrx.com

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++的理解和掌握，越来越多的程序员可以使用二分法解决实际问题。

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

下一篇: C++11的Lambda表达式

评论区

()

相似文章