C++代码：折半查找法 |21xrx.com

C++代码：折半查找法

2023-07-10 01:14:03 深夜i -- --

C++ 代码折半查找法查找数组

在计算机编程中，折半查找法（Binary Search）是一种高效的搜索算法，也被称为二分查找法。它的基本思想是将有序的数据序列划分成两个部分，逐步缩小搜索范围，最终在序列中找到目标值。

C++是一种强大的编程语言，也非常适合实现折半查找算法。下面就来介绍一下如何使用C++编写折半查找算法。

折半查找算法的核心在于每次将搜索区间缩小一半。具体实现时，可以定义两个指针left和right，分别指向数组的开始和结尾。然后对数组进行二分切分，取中间元素并与目标值比较大小，如果相等则直接返回，如果目标值小于中间元素，就将right指针移动到中间元素的左侧，否则将left指针移动到中间元素的右侧。依照此逻辑，不断缩小搜索区间，直到找到目标值或者搜索区间为空。

下面是一份简单的C++代码实现：


#include <iostream>
using namespace std;
int binary_search(int arr[], int target, int n) {
  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) {
      left = mid + 1;
    }
    else
      right = mid - 1;
    
  }
  return -1;
}
int main() {
  int arr[] = 1;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 5;
  int idx = binary_search(arr, target, n);
  if (idx >= 0)
    cout << "Target found at index " << idx << endl;
  
  else
    cout << "Target not found" << endl;
  
  return 0;
}

在以上代码中，我们定义了一个名为binary_search的函数，接收一个整数数组、目标值和数组长度作为参数，并返回目标值在数组中的下标，如果找不到则返回-1。在函数中，我们定义了左右指针left和right，并将它们初始化为数组的开始和结尾。之后，我们使用while循环缩小搜索区间，直到搜索区间缩小为0。在每次循环中，我们取当前搜索区间的中间元素arr[mid]，并与目标值进行比较。如果相等，则返回mid，表示找到了目标值；如果目标值小于arr[mid]，则将右指针right移动到mid的左侧，缩小搜索区间的范围；如果目标值大于arr[mid]，则将左指针left移动到mid的右侧，同样缩小搜索区间的范围。如果搜索到最后还没有找到目标值，则返回-1。

在main函数中，我们定义了一个整数数组arr，将目标值设置为5，然后调用binary_search函数进行搜索，并将结果存入idx变量。最后，我们根据idx的值输出搜索结果。

总的来说，折半查找算法是非常高效的搜索算法，它的时间复杂度为O(logn)，比线性搜索算法要快得多。在实际编程中，使用折半查找算法可以加速程序运行，提高程序的效率。

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

下一篇: 语法错误和逻辑错误

评论区

()

相似文章