非启发式算法第一练——二分、三分搜索算法
非启发式算法是一类不依赖于启发式信息或领域知识的问题解决方法。其中，二分搜索和三分搜索算法是两个经典且广泛应用的技术。在本篇博客中，我们将深入了解这两种搜索算法的原理、应用场景以及如何在实际问题中使用它们。
二分搜索算法
原理
二分搜索算法，又称为二分查找，是一种高效的搜索方法。它基于分治思想，适用于已排序的数组或列表。其核心思想是在每一步中将搜索区间缩小一半，直到找到目标或区间为空。
步骤
- 确定搜索区间的左右边界。
- 计算中间位置的索引。
- 检查中间元素是否是目标。
- 如果中间元素等于目标，搜索完成。
- 如果中间元素大于目标，将搜索区间缩小为左半部分。
- 如果中间元素小于目标，将搜索区间缩小为右半部分。
- 重复步骤2-6，直到找到目标或区间为空。
应用场景
二分搜索广泛应用于需要在有序数据集中查找元素的场景，例如查找特定值、判定某个条件是否满足等。
示例代码
python
def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # Target not found
Java 实现
public class BinarySearch { // 二分搜索算法 static int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; // 找到目标，返回索引 } else if (arr[mid] < target) { left = mid + 1; // 缩小搜索区间为右半部分 } else { right = mid - 1; // 缩小搜索区间为左半部分 } } return -1; // 目标不在数组中 } public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int target = 5; int result = binarySearch(arr, target); if (result != -1) { System.out.println("Target found at index: " + result); } else { System.out.println("Target not found in the array."); } } }
C++ 实现
#include <iostream> #include <vector> using namespace std; // 二分搜索算法 int binarySearch(vector<int>& arr, int target) { int left = 0, right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; // 找到目标，返回索引 } else if (arr[mid] < target) { left = mid + 1; // 缩小搜索区间为右半部分 } else { right = mid - 1; // 缩小搜索区间为左半部分 } } return -1; // 目标不在数组中 } int main() { vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int target = 5; int result = binarySearch(arr, target); if (result != -1) { cout << "Target found at index: " << result << endl; } else { cout << "Target not found in the array." << endl; } return 0; }
三分搜索算法
原理
三分搜索算法是二分搜索的扩展，用于在凸函数上寻找极值。与二分搜索不同，三分搜索每次将搜索区间分为三个部分，并根据目标函数值的情况确定下一步搜索的方向。
步骤
- 确定搜索区间的左右边界。
- 计算两个中间点，将搜索区间分为三部分。
- 比较两个中间点的函数值。
- 根据函数值的情况，确定搜索区间缩小的方向。
- 重复步骤2-4，直到满足停止条件。
应用场景
三分搜索主要用于寻找单峰函数的极值点，例如求解凸函数的最小值或最大值。
示例代码
python
def ternary_search(func, left, right, epsilon=1e-9): while right - left > epsilon: mid1 = left + (right - left) / 3 mid2 = right - (right - left) / 3 if func(mid1) < func(mid2): right = mid2 else: left = mid1 return (left + right) / 2
Java 实现
public class TernarySearch { // 三分搜索算法 static double ternarySearch(double left, double right, double epsilon) { while (right - left > epsilon) { double mid1 = left + (right - left) / 3; double mid2 = right - (right - left) / 3; double f1 = function(mid1); double f2 = function(mid2); if (f1 < f2) { right = mid2; } else { left = mid1; } } return (left + right) / 2; } // 示例函数（替换成需要寻找极值的函数） static double function(double x) { // 这里替换成实际的函数表达式 return x * x; } public static void main(String[] args) { double result = ternarySearch(-10, 10, 1e-9); System.out.println("The minimum/maximum value is: " + result); } }
C++ 实现
#include <iostream> using namespace std; // 三分搜索算法 double ternarySearch(double left, double right, double epsilon) { while (right - left > epsilon) { double mid1 = left + (right - left) / 3; double mid2 = right - (right - left) / 3; double f1 = function(mid1); double f2 = function(mid2); if (f1 < f2) { right = mid2; } else { left = mid1; } } return (left + right) / 2; } // 示例函数（替换成需要寻找极值的函数） double function(double x) { // 这里替换成实际的函数表达式 return x * x; } int main() { double result = ternarySearch(-10, 10, 1e-9); cout << "The minimum/maximum value is: " << result << endl; return 0; }
结语
二分搜索和三分搜索算法是解决一些特定问题的有力工具。它们的高效性和简单性使它们在算法和编程中得到了广泛的应用。通过深入理解这两种搜索算法的原理和应用场景，我们可以更好地运用它们来解决实际问题。在编写代码时，要根据具体问题选择合适的搜索算法，以提高算法效率。
