查找与二分

查找与二分

二分思想是算法竞赛的核心技巧之一。共 5 个模板。

← 返回模板库

3.1二分查找

在有序数组中高效查找目标值

O(log n)

3.2二分答案 - 伐木工

将最优化问题转化为判定问题

O(n log n)

3.3实数二分

在实数范围内进行二分搜索

O(log(precision))

3.4三分法

求单峰/单谷函数的极值

O(log n)

3.5ST表 - RMQ问题

静态区间最值查询，预处理后O(1)查询

O(n log n) 预处理, O(1) 查询