33DAI：批量导入三三文档

2026-05-20T18:24:02Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第87行：		第87行：
	[[Category:进阶算法]]		[[Category:进阶算法]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:17Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 二分查找 ==

在'''有序序列'''中查找目标值，每次将搜索范围缩小一半，时间复杂度 <math>O(\log n)</math>。

=== 二分查找模板 ===

<syntaxhighlight lang="cpp">
// 在有序数组 a 中查找第一个 >= x 的位置（lower_bound）
int lower_bound(int a[], int n, int x)
{
int l = 1, r = n, ans = n + 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (a[mid] >= x)
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return ans;
}
</syntaxhighlight>

=== 查找最后一个 <= x 的位置 ===

<syntaxhighlight lang="cpp">
int upper_bound(int a[], int n, int x)
{
int l = 1, r = n, ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (a[mid] <= x)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return ans;
}
</syntaxhighlight>

== 二分答案 ==

当问题满足'''单调性'''时，可以对答案进行二分，验证当前答案是否可行。

=== 典型场景 ===

* 最大值最小化 / 最小值最大化
* 判断是否存在一种方案满足某个条件

=== 模板 ===

<syntaxhighlight lang="cpp">
auto check = [&](int mid) -> bool
{
// 判断答案 mid 是否可行
return true; // or false
};

int l = 1, r = max_value, ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
l = mid + 1; // 或 r = mid - 1，取决于求最大还是最小
}
else
{
r = mid - 1;
}
}
</syntaxhighlight>

[[Category:进阶算法]]
[[Category:三三文档]]

09-进阶算法/04-二分查找与二分答案 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档