跳转至

二分

二分法

二分查找

二分搜索,也称折半搜索、二分查找,是用来在一个有序数组中查找某一元素的算法。

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

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

在二分搜索过程中,每次都把查询的区间减半,因此对于一个长度为 n的数组,至多会进行 O(\log n)次查找。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;  // 单一出口
}
Note

>> 1/ 2 速度快一些

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

如果我们要求满足某种条件的最大值的最小可能情况(最大值最小化)呢?首先的想法是从小到大枚举这个作为答案的「最大值」,然后去判断是否合法。要是这个答案是单调的就好了,那样就可以使用二分搜索法来更快地找到答案。

要想使用二分搜索法来解这种「最大值最小化」的题目,需要满足以下三个条件:

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

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

二分法把一个寻找极值的问题转化成一个判定的问题(用二分搜索来找这个极值)。类比枚举法,我们当时是枚举答案的可能情况,现在由于单调性,我们不再需要一个个枚举,利用二分的思路,就可以用更优的方法解决「最大值最小」、「最小值最大」。这种解法也成为是「二分答案」,常见于解题报告中。

STL 的二分查找

补充一个小知识点,对于一个有序的 array 你可以使用 std::lower_bound() 来找到第一个大于等于你的值的数, std::upper_bound() 来找到第一个大于你的值的数。

请注意,必须是有序数组,否则答案是错误的。

关于具体使用方法,请参见 STL 页面

二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。如果我们把这里的枚举换成二分,就变成了“二分答案”。

来看一看一道例题 Luogu P1873 砍树,我们可以在 1 到 1000000000(10 亿)中枚举答案,但是这种朴素写法肯定拿不到满分,因为从 1 跑到 10 亿太耗时间。我们可以对答案进行 1 到 10 亿的二分,其中,每次都对其进行检查可行性(一般都是使用贪心法)。 这就是二分答案。

下面就是例题的参考答案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 x) {
  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(m);
  return 0;
}

看完了上面的代码,你肯定会有两个疑问:

  1. 为何搜索区间是左闭右开的?

    因为搜到最后,会这样(以合法的最大值为例):

    然后会

    合法的最小值恰恰相反。

  2. 为何返回左边值?

    如上图

三分法

1
2
3
4
5
6
lmid = left + (right - left >> 1);
rmid = lmid + (right - lmid >> 1);  // 对右侧区间取半
if (cal(lmid) > cal(rmid))
  right = rmid;
else
  left = lmid;

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

画一下图好理解一些(图待补)

  • 如果 lmidrmid 在最大(小)值的同一侧: 那么由于单调性,一定是二者中较大(小)的那个离最值近一些,较远的那个点对应的区间不可能包含最值,所以可以舍弃。
  • 如果在两侧: 由于最值在二者中间,我们舍弃两侧的一个区间后,也不会影响最值,所以可以舍弃。

分数规划

分数规划是这样一类问题,每个物品有两个属性 c_id_i,要求通过某种方式选出若干个,使得 \frac{\sum{c_i}}{\sum{d_i}}最大或最小。

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

二分法

比如说我们要求的是最小的,记 L为最优的答案,对这个式子做一些变换:

L \geq \frac{\sum{c_i}}{\sum{d_i}}

把分母乘过去,把右侧化为 0

{\sum{d_i}} \times L - {\sum{c_i}} \geq 0

即:

{\sum_{i=1}^N{d_i}} \times L - {\sum_{i=1}^N{c_i}} \geq 0
\sum_{i=1}^N{d_i \times L - c_i} \geq 0

不难发现,如果 L'L要小,上式左端的值会更大一些。

所以要求得最小的 L,我们要求的就变成了让上式左端最接近 0L

不难发现左端的式子是随 L变化而单调变化的,所以可以通过二分法来解决。

Dinkelbach 算法

Dinkelbach 算法的大概思想是每次用上一轮的答案当做新的 L来输入,不断地迭代,直至答案收敛。


评论