C++代码实现的折半查找法 |21xrx.com

C++代码实现的折半查找法

2023-06-23 18:58:06 深夜i -- --

C++ 折半查找二分查找有序数组

在计算机程序设计中，折半查找法也叫二分查找法，是一种常用的查找算法。其基本思想是在有序序列中进行查找，将问题规模折半缩小，通过比较中间元素和目标元素的大小来决定查找方向，最终在 $\log_2{n}$ 的时间复杂度内找到目标元素。

在C++中，实现折半查找法的代码如下：


#include <iostream>
int binarySearch(int arr[], int lo, int hi, int key) {
  if (lo <= hi) {    // 基本终止条件
    int mid = (lo + hi) / 2;
    if (arr[mid] == key) return mid;      // 查找成功
    else if (arr[mid] > key) return binarySearch(arr, lo, mid - 1, key); // 在左半部分查找
    else return binarySearch(arr, mid + 1, hi, key);           // 在右半部分查找
  }
  return -1; // 查找失败
}
int main() {
  int arr[] = 6;
  int n = sizeof(arr) / sizeof(int);
  int key = 13;
  int index = binarySearch(arr, 0, n - 1, key);
  if (index != -1)
    std::cout << "查找成功
  else 元素" << key << "不存在" << std::endl;
  
  return 0;
}

在以上代码中，`binarySearch()`函数接受一个有序数组、搜索范围的左右端点和需要查找的元素，返回元素所在下标（从0开始），如果未找到，则返回-1。函数的基本终止条件是当左右端点相等或者左端点大于右端点时，说明已经在数组中查找完毕，但依然未找到目标元素，此时返回-1；如果中间元素与目标元素相等，则查找成功，并返回中间元素的下标；否则依据中间元素与目标元素的大小关系，递归地将查找范围折半缩小。

通过上述代码，我们可以很轻松地在一个有序数组中查找给定元素，大大提高了程序的效率。实际上，折半查找法很常见，常用于数据检索系统、计算科学和数学工程等领域中，是实现高效算法的重要手段之一。

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

下一篇: C++作用域:了解C++编程中不同作用域的含义和用法

评论区

()

相似文章