二分与三分

二分查找

二分查找是一种在有序数组中查找特定元素的搜索算法。

特点

1. 时间复杂度：
2. 空间复杂度：
3. 适用于有序数组的查找和边界确定

分类

二分答案

二分答案是一种通过二分搜索可能解来找到最优解的技术。

特点

1. 时间复杂度：，其中 是判定的复杂度
2. 空间复杂度：与判定函数相关
3. 适用于最大值最小化或最小值最大化问题

分类

三分查找

三分查找是一种用于查找单峰函数极值的搜索算法。

特点

1. 时间复杂度：
2. 空间复杂度：
3. 适用于单峰/单谷函数的极值查找

分类

应用场景对比

二分查找适合：

1. 有序数组查找
2. 边界值确定
3. 旋转数组查找
4. 插入位置查找

二分答案适合：

1. 最大值最小化
2. 最小值最大化
3. 资源分配问题
4. 调度问题优化

三分查找适合：

1. 单峰函数极值
2. 凸/凹函数最值
3. 距离最值问题
4. 最优分割点查找

选择建议

1. 有序数组查找选择二分查找
2. 最优化问题考虑二分答案
3. 单峰函数极值选择三分查找
4. 需要精确解时选择整数二分
5. 需要近似解时选择实数二分