三分查找
入门适合单峰/单谷函数求极值，是二分查找的变体。
// 搜索输入
定义数组和目标值
可视化演示开发中
三分查找 的交互式动画即将上线，敬请期待。
1int ternarySearch(int arr[], int n, int target) {
2 int left = 0, right = n - 1;
3 while (right - left > 2) {
4 int third = (right - left) / 3;
5 int mid1 = left + third;
6 int mid2 = right - third;
7 if (arr[mid1] == target) return mid1;
8 if (arr[mid2] == target) return mid2;
9 if (arr[mid1] < target)
10 left = mid1 + 1;
11 else
12 right = mid2 - 1;
13 }
14 for (int i = left; i <= right; i++)
15 if (arr[i] == target) return i;
16 return -1;
17}
复杂度分析
时间 O(log n)
空间 O(1)
最优 O(1)
最坏 O(log n)
算法讲解
三分查找将区间 [left, right] 分为三段，得到两个中间点 mid1 和 mid2。
通过比较 mid1 和 mid2 处的值，可以判断极值在哪一段。
每次迭代可以排除 1/3 的区间，时间复杂度为 O(log₃n)。
它特别适合在单峰函数上寻找最大值或最小值。