21xrx.com
2025-03-27 04:19:16 Thursday
文章检索 我的文章 写文章
C++中的二分查找算法
2023-07-01 13:08:38 深夜i     10     0
- 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表示未找到。

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

  
  

评论区