二分入门
最新回答
西羊夕下
2026-05-20 12:51:38
二分查找的核心思想是通过不断缩小搜索范围来定位目标值或满足特定条件的解。其基本步骤如下：
- 初始化边界：设定初始的搜索范围，通常为数组的起始和结束索引。
- 计算中间点：在当前的搜索范围内计算中间点的索引。
- 比较中间点与目标值：
如果中间点的值等于目标值，则返回该索引。
如果中间点的值小于目标值，调整左边界以搜索右半部分。
如果中间点的值大于目标值，调整右边界以搜索左半部分。
- 重复步骤：重复上述过程，直到找到目标值或搜索范围为空。
在处理重复元素时，二分查找可以进一步优化以找到第一个或最后一个出现的目标值：
寻找第一个出现的目标值：
当中间点的值大于或等于目标值时，继续在左半部分搜索。
这样可以确保找到的是第一个出现的目标值。
寻找最后一个出现的目标值：
当中间点的值小于或等于目标值时，继续在右半部分搜索。
这样可以确保找到的是最后一个出现的目标值。
二分查找不仅限于查找特定值，还可以用于查找满足特定条件的最优解：
- 查找满足条件的最小值或最大值：
通过调整二分查找的条件，可以找到满足某个条件的最小或最大值。
例如，在分配糖果的问题中，通过二分查找确定每个孩子能获得的最大糖果数。
在实现二分查找时，需要注意以下几点：
- 边界条件的处理：确保在每次调整边界时，搜索范围仍然有效，避免无限循环。
- 中间点的计算：在寻找最后一个出现的目标值时，中间点的计算可能需要调整以避免死循环。
- 循环的终止条件：根据具体问题选择合适的循环终止条件，如 while (l < r) 或 while (l <= r)。
示例代码分析：
查找第一个出现的目标值：
int l = 0, r = n;while (l < r) { int mid = (l + r) / 2; if (a[mid] < value) { l = mid + 1; } else { r = mid; }}当 a[mid] < value 时，调整左边界；否则调整右边界。
最终 l 和 r 会指向第一个出现的目标值。
查找最后一个出现的目标值：
int l = 0, r = n;while (l < r) { int mid = (l + r + 1) / 2; // 避免死循环 if (a[mid] > value) { r = mid - 1; } else { l = mid; }}当 a[mid] > value 时，调整右边界；否则调整左边界。
中间点的计算通过 +1 避免死循环。
查找满足条件的最优解：
ll l = 1, r = L;ll ans = 0;while (l <= r) { ll mid = (l + r) / 2; if (judge(a, mid, M)) { ans = mid; l = mid + 1; } else { r = mid - 1; }}通过 judge 函数验证当前中间点是否满足条件。
根据验证结果调整边界，逐步逼近最优解。
总结：
- 基本二分查找：用于在有序数组中查找特定值。
- 处理重复元素：通过调整边界条件，可以找到第一个或最后一个出现的目标值。
- 查找最优解：通过结合条件验证，可以找到满足特定条件的最小或最大值。
- 实现细节：注意边界条件的处理和中间点的计算，避免死循环和无效搜索。
通过灵活应用二分查找的思想，可以高效解决多种查找和优化问题。
热门标签
