C++二分查找算法代码 |21xrx.com

C++二分查找算法代码

2023-06-29 09:17:55 深夜i -- --

C++ 二分查找算法代码

C++中的二分查找算法是一种常用的搜索算法，用于在有序数组中查找目标元素。它的时间复杂度为O(log n)，比线性搜索算法要高效得多。下面是C++中实现二分查找的代码示例：

 C++
int binary_search(vector<int> &arr, int target) {
  int low = 0, high = arr.size() - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target)
      return mid;
     else if (arr[mid] < target) {
      low = mid + 1;
    } else
      high = mid - 1;
    
  }
  return -1; // not found
}

该算法的思路是首先设定一个搜索范围（区间）[low, high]，然后计算中间位置mid，分析mid与目标元素的大小关系，根据这个关系更新low、high的值，然后继续在新的区间中查找，直至找到目标元素或者搜索区间为空（即low > high）时结束查找。如果未找到目标元素，则返回-1。

在使用该代码时，我们需要将需要查找的有序数组传入函数中，以及目标元素的值target。对于返回的结果，如果返回值为-1，说明目标元素不在数组中，否则返回的是目标元素在数组中的位置。需要注意的是，该算法要求有序数组，如果传入的数组不是有序的，需要先对数组进行排序操作。

可以使用如下代码进行测试：

 C++
int main() {
  vector<int> arr 9;
  int target = 5;
  int index = binary_search(arr, target);
  if (index == -1)
    cout << "not found" << endl;
   else
    cout << "found at position " << index << endl;
  
  return 0;
}

通过该示例代码，我们可以看到，二分查找算法可以快速准确地查找有序数组中的目标元素。在实际项目中，如果需要查找某个元素是否在一个大型有序数据集合中，则C++中的二分查找算法是一个高效可靠的选择。

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

下一篇: C++函数指针的定义

评论区

()

相似文章