二分 - 算法基础

本页面将简要介绍二分查找，由二分法衍生的三分法以及二分答案。

## 二分法

### 简介

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

### 工作原理

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

### 性质

#### 时间复杂度

二分查找的最优时间复杂度为 $O(1)$ 。

二分查找的平均时间复杂度和最坏时间复杂度均为 $O(\log n)$ 。因为在二分搜索过程中，算法每次都把查询的区间减半，所以对于一个长度为 $n$ 的数组，至多会进行 $O(\log n)$ 次查找。

#### 空间复杂度

迭代版本的二分查找的空间复杂度为 $O(1)$ 。

递归（无尾调用消除）版本的二分查找的空间复杂度为 $O(\log n)$ 。

### 代码实现

```cpp
int binary_search(int start, int end, int key) {
	int ret = -1;	// 未搜索到数据返回-1下标
	int mid;
	while (start <= end) {
		mid = start + ((end - start) >> 1);	// 直接平均可能会溢出，所以用这个算法
		if (arr[mid] < key)
			start = mid + 1;
		else if (arr[mid] > key)
			end = mid - 1;
		else {	// 最后检测相等是因为多数搜索情况不是大于就是小于
			ret = mid;
			break;
		}
	}
	return ret;	// 单一出口
}
```

###
> 对于 $n$ 是有符号数的情况，当你可以保证 $n\ge 0$ 时， `n >> 1` 比 `n / 2` 指令数更少。

### 最大值最小化

注意，这里的有序是广义的有序，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做 $1$ ，不满足看做 $0$ ，至少对于这个条件的这一维度是有序的）。换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值。

要求满足某种条件的最大值的最小可能情况（最大值最小化），首先的想法是从小到大枚举这个作为答案的「最大值」，然后去判断是否合法。若答案单调，就可以使用二分搜索法来更快地找到答案。因此，要想使用二分搜索法来解这种「最大值最小化」的题目，需要满足以下三个条件：

1. 答案在一个固定区间内；
2. 可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；
3. 可行解对于区间满足一定的单调性。换言之，如果 $x$ 是符合条件的，那么有 $x + 1$ 或者 $x - 1$ 也符合条件。（这样下来就满足了上面提到的单调性）

当然，最小值最大化是同理的。

### STL 的二分查找

C++ 标准库中实现了查找首个不小于给定值的元素的函数 [ `std::lower_bound` ](https://zh.cppreference.com/w/cpp/algorithm/lower_bound) 和查找首个大于给定值的元素的函数 [ `std::upper_bound` ](https://zh.cppreference.com/w/cpp/algorithm/upper_bound) ，二者均定义于头文件 `<algorithm>` 中。

二者均采用二分实现，所以调用前必须保证元素有序。

### 二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了“二分答案”。

### "[Luogu P1873 砍树](https://www.luogu.com.cn/problem/P1873)"
> 伐木工人米尔科需要砍倒 M 米长的木材。这是一个对米尔科来说很容易的工作，因为他有一个漂亮的新伐木机，可以像野火一样砍倒森林。不过，米尔科只被允许砍倒单行树木。
> 
> 米尔科的伐木机工作过程如下：米尔科设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有的树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。米尔科就行到树木被锯下的部分。
> 
> 例如，如果一行树的高度分别为 20，15，10 和 17，米尔科把锯片升到 15 米的高度，切割后树木剩下的高度将是 15，15，10 和 15，而米尔科将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
> 
> 米尔科非常关注生态保护，所以他不会砍掉过多的木材。这正是他为什么尽可能高地设定伐木机锯片的原因。帮助米尔科找到伐木机锯片的最大的整数高度 H，使得他能得到木材至少为 M 米。换句话说，如果再升高 1 米，则他将得不到 M 米木材。

### "解题思路"
> 我们可以在 1 到 1,000,000,000（10 亿）中枚举答案，但是这种朴素写法肯定拿不到满分，因为从 1 跑到 10 亿太耗时间。我们可以对答案进行 1 到 10 亿的二分，然后，每次都对其进行检查可行性（一般都是使用贪心法）。 **这就是二分答案。**

### "参考代码"
```cpp
		int a[1000005];
		int n, m;
		bool check(int k) {	// 检查可行性，k为锯片高度
			long long sum = 0;
			for (int i = 1; i <= n; i++)			 // 检查每一棵树
				if (a[i] > k)										// 如果树高于锯片高度
					sum += (long long)(a[i] - k);	// 累加树木长度
			return sum >= m;									 // 如果满足最少长度代表可行
		}
		
		int find() {
			int l = 1, r = 1000000001;	// 因为是左闭右开的，所以10亿要加1
			while (l + 1 < r) {				 // 如果两点不相邻
				int mid = (l + r) / 2;		// 取中间值
				if (check(mid))					 // 如果可行
					l = mid;								// 升高锯片高度
				else
					r = mid;	// 否则降低锯片高度
			}
			return l;	// 返回左边值
		}
		
		int main() {
			cin >> n >> m;
			for (int i = 1; i <= n; i++) cin >> a[i];
			cout << find();
			return 0;
		}
```
		
		看完了上面的代码，你肯定会有两个疑问：
		
		1.	为何搜索区间是左闭右开的？
		
				因为搜到最后，会这样（以合法的最大值为例）：
		
				![](../images/binary-final-1.png)
		
				然后会
		
				![](../images/binary-final-2.png)
		
				合法的最小值恰恰相反。
		
		2.	为何返回左边值？
		
				同上。

## 三分法

### 简介

三分法可以用来查找凸函数的最大（小）值。

画一下图好理解一些（图待补）

- 如果 `lmid` 和 `rmid` 在最大（小）值的同一侧：由于单调性，一定是二者中较大（小）的那个离最值近一些，较远的那个点对应的区间不可能包含最值，所以可以舍弃。
- 如果在两侧：由于最值在二者中间，我们舍弃两侧的一个区间后，也不会影响最值，所以可以舍弃。

### 代码实现

```cpp
lmid = left + (right - left >> 1);
rmid = lmid + (right - lmid >> 1);	// 对右侧区间取半
if (cal(lmid) > cal(rmid))
	right = rmid;
else
	left = lmid;
```

## 分数规划

参见： [分数规划](/misc/frac-programming/)

分数规划通常描述为下列问题：每个物品有两个属性 $c_i$ ， $d_i$ ，要求通过某种方式选出若干个，使得 $\frac{\sum{c_i}}{\sum{d_i}}$ 最大或最小。

经典的例子有最优比率环、最优比率生成树等等。

分数规划可以用二分法来解决。

WIKIOI

二分 - 算法基础