【打卡D6】二分法
整数二分算法模板 —— 模板题 AcWing 789. 数的范围
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int left_search(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足某种性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int right_search(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;注意:有+就有-
}
return l;
}
二分法(Binary Search)详解
二分法(Binary Search)是一种经典的 分治算法,常用于在 已排序的数组 或 区间 中查找目标值。其核心思想是通过不断将搜索区间对半分,缩小查找范围,从而 高效 地找到目标元素。二分法的时间复杂度是 O(log n),因此在处理大规模数据时非常高效。
基本思想
二分查找的核心思路是:
- 将待查找的区间分成两部分,根据中间元素与目标值的比较结果决定下一步搜索的区间。
- 继续在新的一半区间内查找,不断缩小查找的范围,直到找到目标元素,或确认目标元素不在数组中。
基本步骤
- 初始化区间:设定两个边界,通常是 左边界
l
和 右边界r
,表示当前查找的范围。 - 计算中间位置
mid
:每次计算中间位置mid = (l + r) / 2
(或者使用mid = l + (r - l) / 2
来防止溢出)。 - 比较中间值与目标值:
- 如果中间值等于目标值,则 找到了目标。
- 如果中间值大于目标值,则目标值可能在中间值的左侧,因此 将右边界
r
移动到mid - 1
。 - 如果中间值小于目标值,则目标值可能在中间值的右侧,因此 将左边界
l
移动到mid + 1
。
- 停止条件:当 左边界
l
不再小于右边界r
,说明找到了目标,或者目标不在数组中。
例:假设数组 a = {1, 2, 2, 3, 3, 3, 4, 5, 5}
,并查询 x = 3,
左边界和右边界的位置
-
查找左边界:
- 使用
searchleft(0, 8, 3)
,通过二分查找,返回第一个3
出现的位置,结果是3
。
- 使用
-
查找右边界:
- 使用
searchright(0, 8, 3)
,通过二分查找,返回最后一个3
出现的位置,结果是5
。
- 使用
-
输出:
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10; // 定义数组大小的上限
int a[N]; // 数组,用来存储输入的已排序整数
// 左边界
int searchleft(int l, int r, int x) {
while (l < r) { // 当左右边界还未收敛时
int mid = (r + l) >> 1; // 计算中间位置
if (a[mid] >= x) r = mid; // 如果中间值大于等于 x,则右边界收缩
else l = mid + 1; // 如果中间值小于 x,则左边界收缩
}
return l; // 返回左边界位置,表示第一个大于等于 x 的位置
}
// 右边界
int searchright(int l, int r, int x) {
while (l < r) { // 当左右边界还未收敛时
int mid = (l + r + 1) >> 1; // 计算中间位置,偏向右侧
if (a[mid] <= x) l = mid; // 如果中间值小于等于 x,则左边界收缩
else r = mid - 1; // 如果中间值大于 x,则右边界收缩
}
return r; // 返回右边界位置,表示最后一个小于等于 x 的位置
}
int main() {
int n, q; // n 为数组的长度,q 为查询次数
cin >> n >> q; // 输入数组长度和查询次数
for (int i = 0; i < n; i++) cin >> a[i]; // 输入已排序数组
while (q--) { // 循环处理每一个查询
int x; // 当前查询的目标数字
cin >> x; // 输入要查询的数字 x
// 查找第一个大于等于 x 的位置,使用左边界二分查找
int l = searchleft(0, n - 1, x);
// 如果 l 指向的不是 x,说明数组中没有 x
if (a[l] != x) {
cout << "-1 -1" << endl; // 输出 -1 -1,表示 x 不在数组中
} else {
// 查找最后一个小于等于 x 的位置,使用右边界二分查找
int r = searchright(0, n - 1, x);
// 输出左边界和右边界,即 x 的第一次和最后一次出现的位置
cout << l << " " << r << endl;
}
}
return 0; // 返回 0,程序正常结束
}