三分查找算法：原理、C語言實現與凸性函數應用場景

算法原理

二分查找將區間對半分割，要求序列單調；三分查找將區間三等分，得到兩個中點 mid1、mid2，根據目標值與兩中點值的大小關係，縮小至 1/3 區間。適用於單峰/凸性函數的極值搜索，而非一般有序查找（二分已最優）。

C語言實現：有序數組查找演示

#include <stdio.h>
#define N 10

int main(void) {
    int a[N] = {1,2,3,4,5,6,7,8,9,10};
    int target, left = 0, right = N - 1;
    int mid1, mid2, found = 0;

    printf("輸入查找值: ");
    scanf("%d", &target);

    while (left <= right) {
        mid1 = left + (right - left) / 3;
        mid2 = right - (right - left) / 3;

        if (target == a[mid1] || target == a[mid2]) {
            found = 1; break;
        }
        else if (target < a[mid1]) right = mid1 - 1;
        else if (target > a[mid2]) left = mid2 + 1;
        else { left = mid1 + 1; right = mid2 - 1; } // 落在中間區間
    }

    if (found) {
        if (target == a[mid1]) printf("找到 %d @ 下標 %d\n", target, mid1);
        else printf("找到 %d @ 下標 %d\n", target, mid2);
    } else printf("不存在 %d\n", target);
    return 0;
}

關鍵修正：原代碼邏輯錯誤

原代碼條件 else if (n < a[mid1] && n > a[mid2]) 恆為假（mid1 < mid2 且數組遞增），正確邏輯見上。

真正用武之地：單峰函數極值搜索

對於嚴格單峰函數 f(x)（先遞增後遞減），三分查找可在 O(log n) 找到最大值：

double ternary_search(double l, double r, double (*f)(double)) {
    const double EPS = 1e-9;
    while (r - l > EPS) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) l = m1;   // 峰值在右側
        else r = m2;                 // 峰值在左側
    }
    return (l + r) / 2;
}

應用場景：凸優化問題、拋物線頂點、收益函數最大化等。

二分 vs 三分 選擇指南

總結

三分查找在「有序查找」上無優勢，但在「凸性極值搜索」中不可替代。理解單調性 → 二分、凸性 → 三分的對應關係，才是掌握算法本質的關鍵。