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

C++实现二分查找算法

2023-07-08 05:26:35 深夜i -- --

C++ 二分查找实现算法

二分查找，也被称为折半查找，是一种常见的查找算法。其基本思想是将有序数组等分为两部分，找到中间元素进行比较，如果等于目标值，则查找成功；如果中间元素大于目标值，则继续在左半部分查找；如果中间元素小于目标值，则继续在右半部分查找。重复以上步骤，直到找到目标值或者未找到目标值。

C++是一种常用的编程语言，其提供了丰富的库函数和语法结构，可以实现各种算法和数据结构。下面以C++语言为例，介绍如何实现二分查找算法。

首先，我们需要定义一个函数来实现二分查找。该函数需要输入一个有序数组、数组的长度以及要查找的目标值，并返回目标值在数组中的位置，如果未找到目标值，则返回-1表示查找失败。函数的代码如下：


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

在该函数中，我们首先初始化左右边界left和right，然后使用while循环进行二分查找。在每次循环中，我们计算中间元素的下标mid，如果该元素等于目标值，则查找成功，返回其下标；如果中间元素大于目标值，则缩小右边界，继续在左半部分查找；如果中间元素小于目标值，则缩小左边界，继续在右半部分查找。最终，如果未找到目标值，则返回-1表示查找失败。

我们可以使用以下代码来测试该函数：


int main() {
  int arr[] = 3;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 5;
  int result = binarySearch(arr, n, target);
  if (result != -1)
    cout << "目标值在数组中的位置为：" << result << endl;
   else
    cout << "未找到目标值" << endl;
  
  return 0;
}

在该代码中，我们定义了一个数组arr=5，数组长度为5，要查找的目标值为5。然后调用binarySearch函数进行查找，并根据返回结果判断查找是否成功。如果成功，则输出目标值在数组中的位置，否则输出未找到目标值的提示信息。

综上所述，C++实现二分查找算法的思路较为简单，通过定义一个函数来实现二分查找，可以方便地在有序数组中查找目标值。同时，C++也支持其他查找算法的实现，如顺序查找、哈希查找等。开发者可以根据需要，在C++中选择合适的算法来满足各种实际需求。

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

下一篇: C++解析JSON数组

评论区

()

相似文章