二分查找算法

大家好，我是老马。

今天我们一起来学习一下数组密切相关的三分查找算法。

主要知识

三分查找算法需要拆分下面几个部分：

  1. 入门介绍

  2. 题目练习（按照算法思想分类）– 实际有哪些应用场景？可以解决哪些实际的问题

  3. 和已有知识的关系，比如对比二分查找

  4. 梳理对应的 sdk 包

  5. 应用实战

三分查找介绍

🔍 什么是三分查找（Ternary Search）？

三分查找是一种基于分治思想的搜索算法，专门用于在单峰函数（unimodal function）或单调函数中查找极值（最大值或最小值）。

与二分查找不同的是：

  • 二分查找将区间分成 2 部分；
  • 三分查找将区间分成 3 部分，每次排除 1/3 的区间，保留 2/3 的搜索空间。

🧠 三分查找的适用条件

要使用三分查找，必须满足以下条件之一：

✅ 场景一：一维单峰函数

  • 函数图像先递增后递减，存在一个极大值 peak。

         ▲
    ▲ ▲
   ▲   ▲
  ▲     ▲
 ▲       ▲
▲         ▲

0 1 2 3 4 5 6 ↑ ↑ 左增 右减

✅ 场景二：一维单谷函数（先减后增）

  • 也可用三分查找来找最小值。

🧮 三分查找的原理

假设我们要在区间 [l, r] 中找最大值：

步骤如下：

  1. 取两个三等分点： 
     m1 = l + (r - l) / 3;
 m2 = r - (r - l) / 3;

这样划分为三段： [l, m1], [m1+1, m2-1], [m2, r]

  1. 比较 f(m1) 与 f(m2) 的值：

    • 若 f(m1) < f(m2)，说明峰值一定在 [m1+1, r] 之间：

      l = m1;

    • 若 f(m1) > f(m2)，说明峰值一定在 [l, m2-1] 之间：

      r = m2;

    • 若 f(m1) == f(m2)，可以任选保留 [m1, m2]

  2. 不断迭代，直到区间收缩到足够小（比如长度 ≤3），再暴力查找最大值。

✅ 三分查找的 Java 模板

public int ternarySearch(int[] arr) {
    int l = 0, r = arr.length - 1;
    while (r - l > 2) {
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        if (arr[m1] < arr[m2]) {
            l = m1;
        } else {
            r = m2;
        }
    }

    // 线性查找剩下的几个元素
    int maxIdx = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] > arr[maxIdx]) {
            maxIdx = i;
        }
    }
    return maxIdx;
}

对比二分查找

🆚 与二分查找的对比

特性 二分查找 三分查找
区间划分 两段 三段
每轮排除 1/2 区间 1/3 区间
适用场景 有序数组/找目标值 单峰函数/找极值
查找目标 精确值/是否存在 极大值或极小值（最大/最小索引）
时间复杂度 O(log₂n) O(log₃n) ≈ O(log n)
代码复杂度 简单 略复杂

📌 小结

  • ✅ 三分查找是查找极值的利器，尤其适用于**先增后减（单峰）**的函数或数组。
  • ✅ 实现略复杂于二分查找，但应用场景明确，效果非常好。
  • ✅ 在算法题如 LeetCode 852、找极值的浮点函数题中都可以使用。

应用场景

三分查找（Ternary Search）虽然不如二分查找常见，但在某些类型的算法题中，它非常高效且不可替代。

它主要用于在单峰（或单谷）结构中查找极值，适用于整数数组或连续函数等问题。

✅ 一、三分查找适用的核心场景

场景 描述 示例问题
1️⃣ 单峰数组找最大值 数组先递增后递减，只有一个峰值点（LeetCode 852） 🏔 山脉数组
2️⃣ 单谷数组找最小值 数组先递减后递增，只有一个谷值点 🏞 谷地数组问题
3️⃣ 单调函数求极值（浮点精度） 给定连续函数 f(x)，在区间 [l, r] 内找最大值或最小值 📉 函数最优值问题
4️⃣ 某些构造函数单峰的问题 类似「最小耗费」、「最优分割点」等具有单调性的构造问题 🚀 调整成本最小化
5️⃣ 对撞指针 + 单峰优化的问题 某些双指针问题演化为函数极值问题 🎯 跳跃或滑动窗口极值选择

📌 二、三分查找能解决的问题类型

类型 能解决的问题 示例
✅ 极值点查找 找最大值或最小值 最大收益、峰值点
✅ 最优参数选择 求某函数下的最优 x 最小时间、最小代价
✅ 条件优化问题 某个成本函数在某点最优 跳跃问题、能量问题
✅ 浮点函数优化 二次函数、对数函数等连续函数极值 区间最小值问题

🚀 三、LeetCode 上经典题目

以下是 LeetCode 或相关竞赛平台 上可以用三分查找优化的经典题目：

题号 标题 是否可用三分查找 说明
852 Peak Index in a Mountain Array ✅ 数组先增后减，找峰值索引
162 Find Peak Element ✅（需判断多峰） 找一个「局部峰值」，可用改进版三分
1552 Magnetic Force Between Two Balls ✅ 单调判断函数，最大化最小距离
1283 Find the Smallest Divisor Given a Threshold ✅ 可转换成单峰结构，最小满足条件的值
875 Koko Eating Bananas ✅ 求最小速度，使得吃完香蕉，构成单调性函数
1064 Fixed Point ✅（特殊单调结构） 找到满足 A[i] == i 的点，可用三分
1201 Ugly Number III ✅ 求最小满足条件的数，可以二/三分优化判断函数
1231 Divide Chocolate ✅ 二分最大最小和问题，有最优分割点

✍️ 实战总结

✅ 三分查找 > 用于「极值点查找」

  • 比如找：最大产出、最短耗时、最小代价、最大间距

✅ 特别适合下列题型：

  • 单调 + 极值（最大化最小值、最小化最大值）
  • 「能量值/速度/花费」优化问题
  • 函数形式无法直接使用普通二分查找的情况

小结

希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。

各位极客的点赞收藏转发，是老马持续写作的最大动力！

下一节我们将开始进行相关力扣专题的练习，感兴趣的小伙伴可以关注一波，精彩内容，不容错过。

参考资料

  • 顺序查找

https://www.cnblogs.com/yw09041432/p/5908444.html

https://www.jb51.net/article/53863.htm

https://blog.csdn.net/jiandanokok/article/details/50517837

  • 二分查找

二分搜索算法

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html