C++实现二分查找 |21xrx.com

C++实现二分查找

2023-07-12 17:26:23 深夜i -- --

C++ 二分查找实现

在计算机科学与编程领域，二分查找（Binary Search）是一种非常常见且高效的查找算法，也叫作折半查找。该算法的时间复杂度为O(log n)，意味着该算法的运行时间不随查找范围的大小而线性增长。C++是一种支持高效编程的语言之一，也支持二分查找算法的实现。

二分查找算法的原理十分简单，它将查找范围分为两个部分，通过跟目标数的大小比较来决定下一轮查找的方向。如果目标数比猜测数字小，那么在左边部分继续二分查找，反之则在右边部分继续二分查找。当最终跟目标数的大小相同时，该算法就找到了目标数。

接下来我们以C++代码为例，实现一个简单的二分查找算法:


#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int target) {
  int l = 0, r = n - 1;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (arr[mid] == target)
      return mid;
    else if (arr[mid] < target)
      l = mid + 1;
    else
      r = mid - 1;
  }
  return -1;
}
int main() {
  int arr[10] = 9;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 11;
  int index = binarySearch(arr, n, target);
  if (index >= 0)
    cout << "Target Found at Index: " << index << endl;
  else
    cout << "Target not found in the array." << endl;
  return 0;
}

在上述代码中，我们定义了一个名为binarySearch()的函数来实现二分查找算法。它有三个参数：

- 一个指向整数数组的指针arr；

- 数组的大小n；

- 目标数值target。

该函数的返回值为目标数的下标位置，如果未能找到目标数则返回-1。我们在主函数中定义了一个整型数组arr，其中存储了一组有序的整数，因此我们只需传递该数组的信息以及目标数值给函数binarySearch()，并判断其返回值来判断目标数是否在数组中。

当我们运行上述代码，并设定目标数为11时，程序将输出“Target Found at Index: 5”，也就是目标数在数组中的位置。

以上便是用C++实现二分查找算法的方法。二分查找算法的优点是速度极快，但需要有序数组，否则正常工作将无法保证。因此，在实际编程过程中，我们应该先进行排序操作，然后再实现二分查找算法。

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

下一篇: 如何在C++中让子函数返回两个值？

评论区

()

相似文章