C++中的二分查找算法 |21xrx.com

C++中的二分查找算法

2023-07-01 13:08:38 深夜i -- --

- C++ - 二分查找 - 算法

二分查找算法（Binary Search）是一种非常高效的算法，可用于在已排序的数组或列表中查找特定元素。在C++中，二分查找算法是一种简单易用、广泛应用的算法。它可以在O(log n)的时间内找到指定元素。

二分查找算法的思路是：将数组的中间位置与目标值比较，如果中间位置的值小于目标值，则在数组的后半部分继续查找，反之则在前半部分继续查找。通过不断地缩小查找范围，最终可以找到目标值。

二分查找算法需要满足两个条件：数组必须是有序的，查找范围必须是连续的。

下面是一个简单的C++实现：


int binarySearch(int arr[], int low, int high, int target) {
  while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] == target)
      return mid;
     else if (arr[mid] < target) {
      low = mid + 1;
    } else
      high = mid - 1;
    
  }
  return -1;
}

上面的代码中，`arr`表示要查找的数组，`low`和`high`表示查找范围的开始和结束位置，`target`表示要查找的目标值。在`while`循环中，根据中间元素的值和目标值的大小关系来缩小查找范围。如果找到了目标值，就返回其在数组中的位置（下标），否则返回-1表示未找到。

二分查找算法具有很高的效率，但它的适用范围有一定限制。它只适用于已排序的数组或列表，而且需要占用一定的额外空间。在实际应用中，我们需要根据具体情况选择合适的算法。

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

下一篇: 如何在C++中终止程序

评论区

()

相似文章