当前位置: 首页> 教育> 高考 > 手撕数据结构02--二分搜索(附源码)

手撕数据结构02--二分搜索(附源码)

时间:2025/7/11 20:20:49来源:https://blog.csdn.net/weixin_64593595/article/details/140656864 浏览次数:0次

一、理论基础

二分搜索,也称折半搜索、对数搜索,是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索是一种高效的查找算法,适用于在已排序的数组中查找特定元素。它的基本思想是通过不断将搜索区间对半分割,从而快速缩小查找范围。

二分搜索每次把搜索区域减少一半,时间复杂度为 O(logn)(n代表集合中元素的个数)。

二分搜索的基本步骤如下:

1.初始条件:将搜索范围设为数组的整个区间。
2.查找中间元素:计算当前区间的中间索引。
3.比较中间元素:将中间元素与目标值进行比较:

  • 如果中间元素等于目标值,查找成功,返回中间索引。
  • 如果中间元素小于目标值,将搜索范围缩小到右半部分。
  • 如果中间元素大于目标值,将搜索范围缩小到左半部分。

4.重复步骤 2 和 3,直到找到目标值或搜索范围为空。


在下图中为大家展示了二分搜索的过程:

二、代码实现

#include <iostream>
#include <vector>
using namespace std;int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) 
{if (left <= right) {int mid = left + (right - left) / 2; if (arr[mid] == target) {return mid;}if (arr[mid] > target) {return binarySearchRecursive(arr, left, mid - 1, target);}return binarySearchRecursive(arr, mid + 1, right, target);}return -1;
}int main() 
{vector<int> arr = { 2, 3, 4, 10, 40 };int target = 10;int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);if (result != -1) {cout << "元素在索引 " << result << " 处找到" << endl;}else {cout << "元素未找到" << endl;}return 0;
}

关键字:手撕数据结构02--二分搜索(附源码)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: