C++代码示例：二分查找主函数 |holyya.com

C++代码示例：二分查找主函数

2023-07-11 00:52:39 深夜i -- --

C++ 二分查找主函数示例代码

二分查找（Binary Search）是一种常用的查找算法，其时间复杂度为 O(log n)。这篇文章将展示一个 C++ 代码示例，演示如何在一个有序数组中使用二分查找算法查找一个特定的元素。

首先，我们需要定义一个函数，它将接收两个参数：一个有序数组和要查找的元素。该函数将返回元素在数组中的索引（如果存在），否则返回 -1。以下是二分查找函数的定义：


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

函数将数组的首尾索引分别赋值给变量 low 和 high。接着，它在 while 循环内执行以下操作：

1. 我们计算数组中间元素的索引 mid，它等于 `(low + high) / 2`。

2. 如果中间元素等于目标元素，我们返回其索引 mid。

3. 如果中间元素大于目标元素，我们只需要查找左侧的序列。因此，我们将 high 更新为 mid - 1。

4. 如果中间元素小于目标元素，我们只需要查找右侧的序列。因此，我们将 low 更新为 mid + 1。

5. 如果我们在 while 循环内部找不到目标元素，该函数将返回 -1，表示未找到该元素。

接着，让我们看一个简单的示例，展示如何在一个有序数组中使用该函数查找一个特定的元素。以下是示例代码：


#include<iostream>
using namespace std;
int binarySearch(int arr[], int target, int arr_len);
int main() {
  int arr[] = 10;
  int arr_len = sizeof(arr) / sizeof(arr[0]);
  int target = 8;
  int result = binarySearch(arr, target, arr_len);
  if (result == -1)
    cout << "Element not found in the array" << endl;
   else
    cout << "Element found at index " << result << endl;
  
  return 0;
}
int binarySearch(int arr[], int target, int arr_len) {
  int low = 0;
  int high = arr_len - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] == target)
      return mid;
     else if (arr[mid] > target)
      high = mid - 1;
     else {
      low = mid + 1;
    }
  }
  return -1;
}

输出结果将为 "Element found at index 3"，因为 8 的索引为 3。

在本文中，我们演示了 C++ 中二分查找算法的实现，以及如何使用该算法从一个有序数组中查找元素。通过使用这个算法，我们可以在很短的时间内在大型数据集中查找元素，从而提高程序的效率。

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

下一篇: Node.js键盘操作工具

评论区

()

相似文章