模仿二分查找设计一个三分查找

三分查找可以用于单峰函数的最值问题，其基本思路是将搜索区间分成三个部分，分别判断目标值可能出现的位置，并将搜索区间缩小至可能包含目标值的那一部分。

以下是三分查找的伪代码：

function ternary_search(left, right):
    while left <= right:
        # 将搜索区间分为三个部分
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3

        # 判断目标值可能出现的位置
        if f(mid1) < f(mid2):
            left = mid1 + 1
        else:
            right = mid2 - 1

    # 返回最小值或最大值
    return f(left)

其中 `f(x)` 表示单峰函数，即在某个位置左侧单调递增，在该位置右侧单调递减的函数。在每次迭代中，将搜索区间分为三个部分，分别为 `[left, mid1]`，`(mid1, mid2)`，和 `[mid2, right]`。如果 `f(mid1) < f(mid2)`，说明目标值可能在右侧，因此将左端点更新为 `mid1 + 1`；否则说明目标值可能在左侧，因此将右端点更新为 `mid2 - 1`。最终返回左端点或右端点所对应的函数值即可。

需要注意的是，三分查找的复杂度为 $O(\log n)$，但常数较大，因此只适用于数据规模较小的问题。