二分
二分算法，也称为二分查找或折半查找，是一种在有序数组中查找特定元素的高效算法。以下是 C++ 中二分算法的相关内容：
算法原理
- 二分算法的基本思想是将有序数组分成两部分，然后将目标值与中间元素进行比较。如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在数组的左半部分继续查找；如果目标值大于中间元素，则在数组的右半部分继续查找。重复这个过程，直到找到目标值或者确定目标值不存在于数组中。
- 通过 不断折半缩小搜索范围 的查找方式，时间复杂度为 O(log n)，需满足：
- 数据存储在 线性结构（如数组）
- 数据必须 有序（升序/降序）
代码实现
以下是一个使用 C++ 实现二分算法的示例代码：
#include <iostream>
#include <vector>
using namespace std;
// 二分查找函数
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
// 避免溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
// 目标值不存在于数组中
return -1;
}
int main() {
vector<int> nums = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 7;
int result = binarySearch(nums, target);
if (result!= -1) {
cout << "目标值 " << target << " 在数组中的索引为：" << result << endl;
}
else {
cout << "目标值 " << target << " 不存在于数组中。" << endl;
}
return 0;
}
复杂度分析
- 时间复杂度：二分算法每次迭代都将搜索区间减半，因此时间复杂度为O(log n)，其中 是n数组的长度。这使得二分算法在处理大规模数据时非常高效。
- 空间复杂度：在上述代码中，除了输入的数组外，只使用了几个额外的变量，如
left、right和mid，它们的数量不随输入规模增长，所以空间复杂度为O(1)。
应用场景
- 数据查找：在有序数组或有序列表中快速查找特定元素，如在电话号码簿、字典等数据结构中查找特定的记录。
- 求解方程：可以用于数值计算中求解方程的根。例如，对于一个单调递增或单调递减的函数，可以通过二分算法来逼近方程的解。
- 优化问题：在一些优化问题中，二分算法可以用于搜索最优解的范围。例如，在寻找最小化或最大化某个目标函数的参数时，可以利用二分算法来缩小搜索空间。
注意事项
- 二分算法要求数据必须是有序的。如果数据是无序的，需要先进行排序操作，这可能会增加额外的时间复杂度。
- 在实现二分算法时，需要注意边界条件的处理，以确保算法的正确性和稳定性。
在库中
C++在STL库中已经封装好了二分算法，我们只需要引入调用即可。
在 <algorithm> 头文件中提供以下关键函数：
| 函数 | 作用 | 返回值 |
|---|---|---|
std::binary_search(beg, end, val) | 检查元素是否存在 | bool |
std::lower_bound(beg, end, val) | 返回第一个 ≥val 的迭代器 | 迭代器 |
std::upper_bound(beg, end, val) | 返回第一个 >val 的迭代器 | 迭代器 |
#include <algorithm>
#include <vector>
int main() {
std::vector<int> nums = {1, 3, 5, 7, 9};
// 查找是否存在
bool exists = std::binary_search(nums.begin(), nums.end(), 5); // true
// 查找插入位置
auto lower = std::lower_bound(nums.begin(), nums.end(), 6); // 指向7
int pos = lower - nums.begin(); // 插入位置索引为3
// 统计元素出现次数
auto upper = std::upper_bound(nums.begin(), nums.end(), 5);
int count = upper - lower; // 1次
}
