二分法（Binary Search）和三分法（Ternary Search）是两种常用的搜索算法，用于在有序数组或有序函数中查找特定值或最优解。
1. 二分法：适用于有序数组或有序函数。
- 概念：将数组或函数的中间元素与目标值进行比较，如果相等，则返回结果；如果目标值小于中间元素，则在左半部分递归地应用二分法；如果目标值大于中间元素，则在右半部分递归地应用二分法。
- 步骤：
1. 初始化左指针 `left` 和右指针 `right` 分别指向数组的开始和结束位置。
2. 计算中间位置 `mid`，将中间元素与目标值进行比较。
3. 如果中间元素等于目标值，则返回结果。
4. 如果目标值小于中间元素，则更新右指针 `right = mid - 1`，并继续在左半部分应用二分法。
5. 如果目标值大于中间元素，则更新左指针 `left = mid + 1`，并继续在右半部分应用二分法。
6. 重复步骤 2-5，直到找到目标值或搜索范围为空。
- 时间复杂度：O(logn)，其中 n 是数组的大小。
- 示例代码：
int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // 目标值不存在 }
2. 三分法：适用于某些特定形式的有序函数，例如凸函数或凹函数。
- 概念：将搜索区间划分为三个等分的部分，然后确定目标值可能的所在区间，并通过比较其中两个中点处的函数值来排除一个区间。然后，在剩下的两个区间中重复应用三分法。
- 步骤：
1. 初始化左指针 `left` 和右指针 `right` 分别指向搜索区间的开始和结束位置。
2. 计算两个中点 `mid1 = left + (right - left) / 3` 和 `mid2 = right - (right - left) / 3`。
3. 分别计算函数在 `mid1` 和 `mid2` 处的值并进行比较。
4. 如果函数在 `mid1` 处的值大于函数在 `mid2` 处的值，则目标值在左半区间，更新右指针为 `right = mid2`。
5. 如果函数在 `mid1` 处的值小于函数在 `mid2` 处的值，则目标值在右半区间，更新左指针为 `left = mid1`。
6. 如果函数在 `mid1` 处的值等于函数在 `mid2` 处的值，则目标值可能在左或右区间，更新左指针为 `left = mid1`，右指针为 `right = mid2`。
7. 重复步骤 2-6，直到找到最优解或搜索区间足够小。
- 时间复杂度：O(logn)，其中 n 是搜索区间的大小。
- 示例代码：
double ternarySearch(double left, double right) { double eps = 1e-6; while (right - left > eps) { double mid1 = left + (right - left) / 3; double mid2 = right - (right - left) / 3; double y1 = function(mid1); // 计算函数在 mid1 处的值 double y2 = function(mid2); // 计算函数在 mid2 处的值 if (y1 < y2) { right = mid2; } else { left = mid1; } } return left; // 返回最优解 }
需要注意的是，二分法和三分法都要求搜索对象是有序的。此外，具体的应用场景还有其他因素需要考虑，例如输入数据的规模和特定问题的性质。在实际使用时，请根据具体问题选择适合的算法。
