5bei.cn大模型教程网
文章目录
隐藏
目录
1. 二分查找的基本原理
核心思想
二分查找（Binary Search）是一种高效的查找算法，其核心在于利用 有序性 和 分治思想：
- 有序性：待搜索序列必须是有序的（通常为升序或降序）。
- 分治思想：每次将搜索区间缩小一半，通过比较目标值与中间元素的大小，排除不可能包含目标的区间。
数学基础
对于长度为 nn 的有序数组，二分查找最多需要：⌊log2n⌋+1⌊log2n⌋+1次比较。
示例：
- n=8n=8 → 最多 4 次比较
- n=1000n=1000 → 最多 10 次比较
适用场景
- 数据结构支持 随机访问（如数组、vector）。
- 数据 有序（若无序需先排序）。
- 存在明确的 判断条件（能判断目标在左半区还是右半区）。
2. 二分查找流程图
流程详解
初始状态（第一排）
-
数组（升序）：[0, 1, 3, 4, 5, 6, 7, 8, 9]
-
指针：low 指向最左端的 0；high 指向最右端的 9。
-
计算中点 mid（ left + (right – left) / 2 = 4）
-
比较：nums[mid] = 4 与目标 8。
- 因为 4
- 收缩区间：把 low 移到 mid + 1，于是新的 low 来 到值 5 所在的位置。
- 新搜索区间为右侧半段（图下方用大括号标出）。
第一次收缩后的搜索（第二排）
-
新区间大致为 [5, 6, 7, 8, 9]（仍是闭区间）。
-
指针：low 指向 5，high 仍指向 9，重新计算 mid，图中 mid 指到值 7。
-
比较：nums[mid] = 7 与目标 8。
- 因为 7
- 收缩区间：low = mid + 1，于是 low 移到值 8 的位置。
- 新搜索区间缩小为 [8, 9]。
第二次收缩后的搜索（第三排）
-
当前区间为 [8, 9]。
-
重新计算 mid，图中把 low、mid、high 都标出：mid 正好落在值 8 上。
-
比较：nums[mid] = 8 与目标 8，命中。
-
返回结果：找到目标元素 8，返回它在数组中的下标（按 0 基下标，这个数组里 8 的下标是 7）
3. 标准二分查找模板（查找目标值）
#include
using namespace std;
int binarySearch(vector& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 闭区间 [left, right]
while (left nums = {2, 5, 7, 9, 12, 15, 18};
int target = 9;
int index = binarySearch(nums, target);
cout 4. 二分查找的变体
4.1 查找左边界（第一个 >= target 的元素）
int findLeftBound(vector& nums, int target) {
int left = 0, right = nums.size() - 1;
int result = nums.size(); // 默认不存在
while (left = target) {
result = mid;
right = mid - 1; // 向左收缩
} else {
left = mid + 1; // 向右收缩
}
}
return result;
}
4.2 查找右边界（最后一个
int findRightBound(vector& nums, int target) {
int left = 0, right = nums.size() - 1;
int result = -1; // 默认不存在
while (left
示例（处理重复元素）
int main() {
vector nums = {1, 3, 3, 3, 5, 7};
int leftIndex = findLeftBound(nums, 3);
int rightIndex = findRightBound(nums, 3);
cout
5. 变体流程对比表
int findRightBound(vector& nums, int target) {
int left = 0, right = nums.size() - 1;
int result = -1; // 默认不存在
while (left int main() {
vector nums = {1, 3, 3, 3, 5, 7};
int leftIndex = findLeftBound(nums, 3);
int rightIndex = findRightBound(nums, 3);
cout | 场景 | 区间定义 | 关键逻辑 | 默认返回值 |
|---|---|---|---|
| 标准查找 | 闭区间 [left, right] | 相等返回 mid | -1 |
| 查找左边界 | 闭区间 | 找到后继续向左收缩 right = mid - 1
|
nums.size() |
| 查找右边界 | 闭区间 | 找到后继续向右收缩 left = mid + 1
|
-1 |
6. 总结
-
二分查找的时间复杂度是 O(log n)，空间复杂度是 O(1)。
-
前提：有序、可随机访问。
-
模板记忆：
- 闭区间写法
while (left - 中点计算
mid = left + (right - left) / 2 - 更新边界时避免死循环
- 闭区间写法
文章来源于互联网:二分查找：理论基础与实战模板
为了应对百度文心一言算法的更新，AI搜索优化公司需要采取一系列策略，以确保其客户在搜索引擎结果页（SERP）中保持竞争力。以下是详细的应对措施： 1. 深入理解算法更新的核心 – 技术解析：公司需要深入分析百度文心一言算法更新的具体内容，包括其对排名机…
