二分法
二分法（Binary Search）是一种常用的搜索算法，可以用来查找有序数组中的元素。它的思想非常简单：将有序数组分成两半，判断要查找的元素在左半边还是右半边，然后递归查找。
具体实现时，我们需要记录数组的左边界 $l$ 和右边界 $r$，以及要查找的元素 $x$。每次取数组的中间位置 $mid=(l+r)/2$，将数组分成两半：左半部分为 $[l, mid-1]$，右半部分为 $[mid+1, r]$。然后，判断要查找的元素 $x$ 和中间位置的元素 $nums[mid]$ 的大小关系，如果 $x>nums[mid]$，说明要查找的元素在右半部分，否则在左半部分。如果相等，说明找到了，返回中间位置 $mid$。如果左右两半部分都没找到，说明要查找的元素不存在于数组中。
下面是用 C++ 实现的二分查找算法：
#include <iostream>
#include <vector>
using namespace std;
int binary_search(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;
}
int main() {
vector<int> nums = {1, 3, 5, 7, 9};
int target = 7;
int idx = binary_search(nums, target);
if (idx != -1) {
cout << "Target " << target << " found at index " << idx << endl;
} else {
cout << "Target " << target << " not found" << endl;
}
return 0;
}在这个例子中，我们首先定义了一个有序数组 nums 和要查找的元素 target。然后，我们调用 binary_search 函数查找元素在数组中的位置。如果找到了，输出元素的位置；否则输出未找到的提示。
需要注意的是，二分法要求数组是有序的。如果数组无序，需要先进行排序。此外，二分法的时间复杂度是 $O(\\log n)$，其中 $n$ 是数组的长度。因为每次查找都会将数组的大小减半，所以最多只需要查找 $\\log n$ 次，即可将数组查找完毕。
二分法还有一些变种，例如左侧二分、右侧二分、插入位置查找等。
左侧二分：
左侧二分的思想是，在找到目标值时，继续向左寻找，直到找到第一个小于目标值的位置。
int left_binary_search(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) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (left < nums.size() && nums[left] == target) {
return left;
} else {
return -1;
}
}右侧二分：
右侧二分的思想是，在找到目标值时，继续向右寻找，直到找到第一个大于目标值的位置。
int right_binary_search(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) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right >= 0 && nums[right] == target) {
return right;
} else {
return -1;
}
}插入位置查找：
插入位置查找的思想是，在没有找到目标值时，返回目标值应该插入的位置。
int searchInsert(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 left;
}这些变种都是在原有二分法的基础上进行的简单修改，但是要注意边界条件的处理。左侧二分和右侧二分可以用于求解一些特定的问题，例如计算逆序对数量。而插入位置查找可以用于在有序数组中插入一个元素，使得数组仍然有序。
除了基本的二分法和变种之外，还有一些高级的二分法算法，例如倍增算法、三分法、计算几何中的二分答案等。
倍增算法：
倍增算法通常用于解决静态区间问题，例如求解静态区间最大值、最小值、区间和等问题。倍增算法的核心思想是预处理出所有可能的区间大小，然后利用已经处理出的区间大小求解更大的区间大小。
const int N = 1e5 + 5;
int n, m;
int a[N];
int f[N][30];
void init() {
for (int i = 1; i <= n; i++) {
f[i][0] = a[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int k = log2(r - l + 1);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}三分法：
三分法通常用于解决单峰函数的最值问题。单峰函数是指在某个位置左侧单调递增，在某个位置右侧单调递减的函数。三分法的核心思想是通过二分的方式确定函数的峰值所在的范围，然后在峰值范围内继续三分求解最值。
double func(double x) {
return -x * x + 10 * x + 2;
}
double ternary_search(double left, double right, double eps) {
while (right - left > eps) {
double m1 = left + (right - left) / 3.0;
double m2 = right - (right - left) / 3.0;
if (func(m1) < func(m2)) {
left = m1;
} else {
right = m2;
}
}
return (left + right) / 2.0;
}二分答案：
二分答案是计算几何中的一种常见技巧，用于解决一些几何问题，例如判断一个点是否在多边形内部、判断两个凸包是否相交等。二分答案的核心思想是二分答案值，在每一次计算中，通过判断二分答案的值是否满足一定的条件来决定二分答案的区间。
