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

C++实现二分查找

2023-06-22 19:17:34 深夜i -- --

C++ 二分查找实现

在计算机中，二分查找是一种常用的搜索算法，也被称为折半查找。C++是一种高级编程语言，它也有内置的函数可以实现二分查找。

二分查找算法的基本思想是将一个有序数组分成两部分，然后根据查找值与中间值的大小关系确定下一步查找的区间。如果查找值等于中间值，那么查找就结束了。如果查找值小于中间值，那么下一步就在左半部分继续查找；如果查找值大于中间值，那么下一步就在右半部分继续查找。

下面是一个简单的C++程序，实现了二分查找算法：


#include<iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
 if (r >= l) {
  int mid = l + (r - l) / 2;
  if (arr[mid] == x)
   return mid;
  if (arr[mid] > x)
   return binarySearch(arr, l, mid - 1, x);
  return binarySearch(arr, mid + 1, r, x);
 }
 return -1;
}
int main()
{
 int arr[] = 2;
 int n = sizeof(arr) / sizeof(arr[0]);
 int x = 10;
 int result = binarySearch(arr, 0, n - 1, x);
 (result == -1) ? cout << "Element is not present in array"
         : cout << "Element is present at index " << result;
 return 0;
}

代表下面的几个相关函数：

- `int binarySearch(int arr[], int l, int r, int x)`：这是二分查找函数的核心部分。它接收四个参数：`arr`表示要查找的数组，`l`表示要查找的数组的起始索引，`r`表示要查找的数组的结束索引，`x`表示要查找的值。如果找到了该值，则返回其索引；否则返回-1。

- `int main()`：这是程序的主函数。它调用了`binarySearch`函数，并打印出返回值。

这个程序的输出应该是“Element is present at index 3”，因为10在数组中的索引为3。

总的来说，C++的二分查找函数是一种非常有用的算法，特别是在需要快速查找大量有序数据时。当然，算法的实现要具体问题具体分析，需要针对不同的数据进行调整。

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

下一篇: C++程序运行时，存储在哪里？

评论区

()

相似文章