三分查找算法C語言實現：原理、代碼與遞歸/迭代對比

三分查找：在凸函數/單峰函數上尋找極值的利器

算法原理

二分查找要求序列單調；三分查找針對凸性(單峰)函數，將區間三等分，通過比較兩個中間點值，縮小搜索範圍至1/3，常用於三元搜索求極值。

C語言迭代實現 (查找有序數組中目標值)

#include <stdio.h>
#define M 10
int ternary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;
        if (arr[mid1] == target) return mid1;
        if (arr[mid2] == target) return mid2;
        if (target < arr[mid1]) right = mid1 - 1;
        else if (target > arr[mid2]) left = mid2 + 1;
        else { left = mid1 + 1; right = mid2 - 1; }
    }
    return -1;
}
int main() {
    int a[M] = {1,2,3,4,5,6,7,8,9,10};
    int x; printf("Input target: "); scanf("%d", &x);
    int pos = ternary_search(a, M, x);
    if (pos >= 0) printf("Found at index %d\n", pos);
    else puts("Not found");
    return 0;
}

關鍵區別：三分查找 vs 二分查找

💡 實戰提示

• 整數數組精確查找二分更簡潔高效，三分常數因子更大。
• 浮點數/連續函數求極值時，三分(三元搜索)是標準解法，迭代100次或直到區間< 1e-9。
• 本文代碼演示的是「在有序數組中查找」的教學版三分，實際工程中極少用於此場景。