C++编写二分查找算法 |21xrx.com

C++编写二分查找算法

2023-07-13 00:36:58 深夜i -- --

C++ 二分查找算法

二分查找算法是经典的算法之一，是在一个有序的列表中查找一个元素的位置。它的优点是查找效率高，时间复杂度为 O(logN)。在实际开发中，我们会经常用到二分查找算法，C++语言可以很好地支持这一算法的实现。

二分查找算法基本原理是在一个有序的列表中找到中间位置的元素，与目标进行比较，如果中间元素大于目标，则去中间元素的左边查找；如果中间元素小于目标，则去中间元素的右边查找。这样不断查找，最终找到目标或者发现目标不在列表中。

实现二分查找算法的关键是确定查找的左右边界。左边界为列表的第一个元素的位置，右边界为列表的最后一个元素的位置。查找过程中，通过计算中间元素的位置不断更新左右边界，最终找到目标元素或者确定目标元素不存在于列表中。

以下是C++语言实现二分查找算法的代码：


#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
  int middle;
  while (left <= right) {
    middle = (left + right) / 2;
    if (arr[middle] == target)
      return middle;
    else if (arr[middle] > target)
      right = middle - 1;
    else
      left = middle + 1;
  }
  return -1;
}
int main() {
  int nums[] = 5;
  int target = 7;
  int left = 0;
  int right = 5;
  int result = binarySearch(nums, left, right, target);
  if (result == -1)
    cout << "元素不存在于列表中";
  else
    cout << "元素存在于列表中，位置为：" << result;
  return 0;
}

以上代码中，binarySearch函数实现二分查找算法，其中arr表示列表，left为左边界，right为右边界，target为查找目标。查找过程中，通过计算中间元素的位置不断更新左右边界，最终找到目标元素或者确定目标元素不存在于列表中。

在main函数中，定义一个包含元素 7的列表nums，并定义目标元素为7。通过调用binarySearch函数，计算左右边界，得到查找结果result。如果结果为-1，说明目标元素不存在于列表中；否则，输出目标元素在列表中的位置。

总之，C++语言提供了很好的支持，实现二分查找算法非常容易。如果你需要在有序列表中查找元素，不妨使用这一算法试试看。

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

下一篇: 《C++编程指南》

评论区

()

相似文章