二分和三分写法总结
2026-10-18 07:35:47
二分和三分是算法中常用的两种搜索方法，分别适用于不同场景。以下是对这两种方法的总结：
二分查找核心思想：在有序数组中查找特定元素，通过不断将搜索区间减半来快速定位目标值。
1. lower_bound（返回第一个大于等于目标值的下标）官方接口：
下标从0开始：int pos = lower_bound(a, a + n, 4) - a
下标从1开始：int pos = lower_bound(a + 1, a + n + 1, 4) - a
自写函数：
int l = 0, r = 8;while (l < r) { int mid = l + r >> 1; if (a[mid] >= value) { r = mid; } else { l = mid + 1; }}关键点：使用>=比较，移动右边界r。
官方接口：
下标从0开始：int pos = upper_bound(a, a + n, 4) - a
下标从1开始：int pos = upper_bound(a + 1, a + n + 1, 4) - a
自写函数（返回最后一个等于目标值的下标）：
int l = 0, r = n;while (l < r) { int mid = l + r + 1 >> 1; if (a[mid] <= value) { l = mid; } else { r = mid - 1; }}关键点：使用<=比较，移动左边界l，且中点计算需加1以避免死循环。
- 方法：将区间翻转，转化为单调递增问题。
核心思想：在单峰或单谷函数中查找极值（最大值或最小值），通过不断将搜索区间分为三部分来缩小范围。
1. 查找凹函数的极小值int l = 1, r = 100;while (l < r) { int lmid = l + (r - l) / 3; int rmid = r - (r - l) / 3; lans = cal(lmid), rans = cal(rmid); if (lans <= rans) { r = rmid - 1; } else { l = lmid + 1; }}cout << min(lans, rans) << endl;- 关键点：
中点计算：左中点l + (r - l) / 3，右中点r - (r - l) / 3。
比较cal(lmid)和cal(rmid)：
若lans <= rans，说明极小值在左侧，移动右边界r。
否则，移动左边界l。
- 关键点：
比较cal(lmid)和cal(rmid)：
若lans <= rans，说明极大值在右侧，移动左边界l。
否则，移动右边界r。
二分查找：
适用于有序数组中的精确查找或边界查找。
需注意边界条件的处理，尤其是中点的计算和边界的移动。
三分查找：
适用于单峰或单谷函数的极值查找。
通过比较两个中点的函数值来缩小搜索范围。
对于小规模数据（如小于100个元素），暴力搜索可能更高效。
二分查找：
lower_bound：查找第一个大于等于目标值的下标。
upper_bound：查找第一个大于目标值的下标。
三分查找：
查找凹函数的极小值。
查找凸函数的极大值。
通过以上总结和图形辅助，可以更直观地理解二分和三分查找的原理和实现细节。
热门标签
