二分查找

概念

  • 二分查找又叫折半查找，利用单调序列的单调性，每次将范围缩小一般，在大规模查找数据的时候有显著优势。
  • 优点：
    • 普通查找的时间复杂度为O(n)，而二分查找的时间复杂度为O(log n)，也就是说百万级别的数据只需要几十次查找就能确定。
    • 在答案的穷举里面有很大的优势，因此引出了二分答案这个概念
  • 缺点：
    • 二分查找只能找具有单调性的序列，对于混乱的数据是没办法查找的

代码实现及注意事项

  • 代码实现：
1
2
3
4
5
6
7
8
9
10
int left=0,right=n-1;
int result=-1;
while(left<=right){
    int mid=(right+left)/2;
    if(a[mid]>=k){
        if(a[mid]==k) result=mid;
        right=mid-1;
    } 
    else left=mid+1;
}

解释： 这里面我们查找的是符合答案的序号最小值，当有符合的答案的时候，我们的right会往左边收缩，也就是right是尝试值，left为确定值，result是来确定是否有答案的，最后left的值和result的值理论上是一样的。

  • 注意事项： 我们这个模板采用了两边都是闭区间的情况，当right==left 的时候，mid=right=left 这是侯mid是合法区间，因此我们要查找这种情况，因此在对while的条件书写的时候，我们是left<=right 而不是left<right
  • 我们要对a[mid]==k 的情况进行判断，我们这个模板是找最小序号，如果想找最大序号，我们就要把mid部分放到else里面，把条件改为a[mid]>k
  • 习题：这里推荐洛谷题单 跳转链接

二分答案

  • 概念： 就是对答案进行二分查找
  • 使用条件： 二分答案的前提是条件的答案具有单调性，同时我们条件具有范围
  • 在洛谷题单里面就有对应的题

三分查找

概念

  • 三分查找是一种用于在单峰函数（先严格递增后严格递减，或先严格递减后严格递增）中寻找极值点的高效算法。

  • 与二分查找每次将区间分为两部分不同，三分查找每次将区间分为三部分，通过比较两个中间点的函数值来缩小搜索范围。

核心思想

  • 对于单峰函数，极值点（最大值或最小值）可以通过不断缩小搜索区间来定位

  • 每次迭代选取两个中间点，根据这两个点的函数值关系，可以确定极值点位于哪个子区间

算法流程

  1. 确定初始区间 [left, right]

  2. 当区间长度足够大时循环：

    • 计算两个中间点：mid1 = left + (right - left) / 3

    • mid2 = right - (right - left) / 3

  3. 比较 f(mid1) 和 f(mid2)：

    • 如果寻找最小值：

      • 若 f(mid1) < f(mid2)，则极值点在 [left, mid2]

      • 若 f(mid1) > f(mid2)，则极值点在 [mid1, right]

      • 若相等，极值点在 [mid1, mid2]

    • 如果寻找最大值：

      • 若 f(mid1) > f(mid2)，则极值点在 [left, mid2]

      • 若 f(mid1) < f(mid2)，则极值点在 [mid1, right]

      • 若相等，极值点在 [mid1, mid2]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 寻找单峰函数的最小值
double ternary_search_min(double left, double right) {
    while (right - left > 1e-7) { // 设置精度阈值
        double mid1 = left + (right - left) / 3;
        double mid2 = right - (right - left) / 3;
        
        if (f(mid1) < f(mid2)) {
            right = mid2; // 最小值在 [left, mid2]
        } else {
            left = mid1;  // 最小值在 [mid1, right]
        }
    }
    return (left + right) / 2;
}
// 寻找单峰函数的最大值
double ternary_search_max(double left, double right) {
    while (right - left > 1e-7) {
        double mid1 = left + (right - left) / 3;
        double mid2 = right - (right - left) / 3;
        
        if (f(mid1) > f(mid2)) {
            right = mid2; // 最大值在 [left, mid2]
        } else {
            left = mid1;  // 最大值在 [mid1, right]
        }
    }
    return (left + right) / 2;
}

整数版本的三分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 整数版本，寻找最小值
int ternary_search_int(int left, int right) {
    while (right - left > 2) { // 至少需要3个点
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;
        
        if (f(mid1) < f(mid2)) {
            right = mid2;
        } else {
            left = mid1;
        }
    }
    
    // 在剩余的小区间内线性搜索
    int min_val = f(left);
    int result = left;
    for (int i = left + 1; i <= right; i++) {
        if (f(i) < min_val) {
            min_val = f(i);
            result = i;
        }
    }
    return result;
}

时间复杂度

  • 时间复杂度：O(log₃n)，其中n为初始区间长度

  • 每次迭代将搜索区间缩小为原来的2/3

  • 虽然底数不同，但时间复杂度仍为对数级别

应用场景

  1. 二次函数极值：抛物线等单峰函数的极值点查找

  2. 几何问题：点到曲线的最短距离

  3. 优化问题：在满足单峰性质的函数中寻找最优解

  4. 物理问题：光的折射路径、最短时间问题等

与二分查找的对比

特性 二分查找 三分查找
适用条件 单调序列 单峰函数
每次比较 1次 2次
区间缩小 1/2 2/3
时间复杂度 O(log₂n) O(log₃n)

注意事项

  1. 单峰性验证：使用前必须确认函数在搜索区间内是单峰的

  2. 精度控制：浮点数版本需要设置合适的精度阈值

  3. 边界处理：整数版本在区间较小时需要转为线性搜索

  4. 函数计算：每次迭代需要计算两次函数值，确保函数计算不耗时

习题推荐

  1. 洛谷 P3382 【模板】三分法

  2. 抛物线最小距离问题

  3. 物理中的最优化问题

三分查找是解决单峰函数极值问题的有力工具，在竞赛和实际问题中都有广泛应用。