跳转至

二分

本頁面將簡要介紹二分查找，由二分法衍生的三分法以及二分答案。

二分法

定義

二分查找（英語：binary search），也稱折半搜索（英語：half-interval search）、對數搜索（英語：logarithmic search），是用來在一個有序數組中查找某一元素的算法。

過程

以在一個升序數組中查找一個數為例。

它每次考察數組當前部分的中間元素，如果中間元素剛好是要找的，就結束搜索過程；如果中間元素小於所查找的值，那麼左側的只會更小，不會有所查找的元素，只需到右側查找；如果中間元素大於所查找的值同理，只需到左側查找。

性質

時間複雜度

二分查找的最優時間複雜度為 \(O(1)\)。

二分查找的平均時間複雜度和最壞時間複雜度均為 \(O(\log n)\)。因為在二分搜索過程中，算法每次都把查詢的區間減半，所以對於一個長度為 \(n\) 的數組，至多會進行 \(O(\log n)\) 次查找。

空間複雜度

迭代版本的二分查找的空間複雜度為 \(O(1)\)。

遞歸（無尾調用消除）版本的二分查找的空間複雜度為 \(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

參考 編譯優化 #位運算代替乘法，對於 \(n\) 是有符號數的情況，當你可以保證 \(n\ge 0\) 時，n >> 1 比 n / 2 指令數更少。

最大值最小化

注意，這裏的有序是廣義的有序，如果一個數組中的左側或者右側都滿足某一種條件，而另一側都不滿足這種條件，也可以看作是一種有序（如果把滿足條件看做 \(1\)，不滿足看做 \(0\)，至少對於這個條件的這一維度是有序的）。換言之，二分搜索法可以用來查找滿足某種條件的最大（最小）的值。

要求滿足某種條件的最大值的最小可能情況（最大值最小化），首先的想法是從小到大枚舉這個作為答案的「最大值」，然後去判斷是否合法。若答案單調，就可以使用二分搜索法來更快地找到答案。因此，要想使用二分搜索法來解這種「最大值最小化」的題目，需要滿足以下三個條件：

  1. 答案在一個固定區間內；
  2. 可能查找一個符合條件的值不是很容易，但是要求能比較容易地判斷某個值是否是符合條件的；
  3. 可行解對於區間滿足一定的單調性。換言之，如果 \(x\) 是符合條件的，那麼有 \(x + 1\) 或者 \(x - 1\) 也符合條件。（這樣下來就滿足了上面提到的單調性）

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

STL 的二分查找

C++ 標準庫中實現了查找首個不小於給定值的元素的函數 std::lower_bound 和查找首個大於給定值的元素的函數 std::upper_bound，二者均定義於頭文件 <algorithm> 中。

二者均採用二分實現，所以調用前必須保證元素有序。

bsearch

bsearch 函數為 C 標準庫實現的二分查找，定義在 <stdlib.h> 中。在 C++ 標準庫裏，該函數定義在 <cstdlib> 中。qsort 和 bsearch 是 C 語言中唯二的兩個算法類函數。

bsearch 函數相比 qsort（排序相關 STL）的四個參數，在最左邊增加了參數「待查元素的地址」。之所以按照地址的形式傳入，是為了方便直接套用與 qsort 相同的比較函數，從而實現排序後的立即查找。因此這個參數不能直接傳入具體值，而是要先將待查值用一個變量存儲，再傳入該變量地址。

於是 bsearch 函數總共有五個參數：待查元素的地址、數組名、元素個數、元素大小、比較規則。比較規則仍然通過指定比較函數實現，詳見 排序相關 STL。

bsearch 函數的返回值是查找到的元素的地址，該地址為 void 類型。

注意：bsearch 與上文的 lower_bound 和 upper_bound 有兩點不同：

  • 當符合條件的元素有重複多個的時候，會返回執行二分查找時第一個符合條件的元素，從而這個元素可能位於重複多個元素的中間部分。
  • 當查找不到相應的元素時，會返回 NULL。

用 lower_bound 可以實現與 bsearch 完全相同的功能，所以可以使用 bsearch 通過的題目，直接改寫成 lower_bound 同樣可以實現。但是鑑於上述不同之處的第二點，例如，在序列 1、2、4、5、6 中查找 3，bsearch 實現 lower_bound 的功能會變得困難。

利用 bsearch 實現 lower_bound 的功能比較困難，是否一定就不能實現？答案是否定的，存在比較 tricky 的技巧。藉助編譯器處理比較函數的特性：總是將第一個參數指向待查元素，將第二個參數指向待查數組中的元素，也可以用 bsearch 實現 lower_bound 和 upper_bound，如下文示例。只是，這要求待查數組必須是全局數組，從而可以直接傳入首地址。

 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
int A[100005];  // 示例全局數組

// 查找首個不小於待查元素的元素的地址
int lower(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) > 0) && compare(a, b) > 0)
    return 1;
  else if (b != A && compare(a, b - 1) <= 0)
    return -1;  // 用到地址的減法，因此必須指定元素類型
  else
    return 0;
}

// 查找首個大於待查元素的元素的地址
int upper(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) >= 0) && compare(a, b) >= 0)
    return 1;
  else if (b != A && compare(a, b - 1) < 0)
    return -1;  // 用到地址的減法，因此必須指定元素類型
  else
    return 0;
}

因為現在的 OI 選手很少寫純 C，並且此方法作用有限，所以不是重點。對於新手而言，建議老老實實地使用 C++ 中的 lower_bound 和 upper_bound 函數。

二分答案

解題的時候往往會考慮枚舉答案然後檢驗枚舉的值是否正確。若滿足單調性，則滿足使用二分法的條件。把這裏的枚舉換成二分，就變成了「二分答案」。

Luogu 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\) 到 \(10^9\) 中枚舉答案，但是這種樸素寫法肯定拿不到滿分，因為從 \(1\) 枚舉到 \(10^9\) 太耗時間。我們可以在 \([1,~10^9]\) 的區間上進行二分作為答案，然後檢查各個答案的可行性（一般使用貪心法）。這就是二分答案。

參考代碼 
 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
27
28
29
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 = 1e9 + 1;   // 因為是左閉右開的，所以 10^9 要加 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. 為何搜索區間是左閉右開的？

    因為搜到最後，會這樣（以合法的最大值為例）：

    然後會

    合法的最小值恰恰相反。

  2. 為何返回左邊值？

    同上。

三分法

引入

如果需要求出單峯函數的極值點，通常使用二分法衍生出的三分法求單峯函數的極值點。

為什麼不通過求導函數的零點來求極值點？

客觀上，求出導數後，通過二分法求出導數的零點（由於函數是單峯函數，其導數在同一範圍內的零點是唯一的）得到單峯函數的極值點是可行的。

但首先，對於一些函數，求導的過程和結果比較複雜。

其次，某些題中需要求極值點的單峯函數並非一個單獨的函數，而是多個函數進行特殊運算得到的函數（如求多個單調性不完全相同的一次函數的最小值的最大值）。此時函數的導函數可能是分段函數，且在函數某些點上可能不可導。

注意

只要函數是單峯函數，三分法既可以求出其最大值，也可以求出其最小值。為行文方便，除特殊説明外，下文中均以求單峯函數的最小值為例。

三分法與二分法的基本思想類似，但每次操作需在當前區間 \([l,r]\)（下圖中除去虛線範圍內的部分）內任取兩點 \(lmid,rmid(lmid < rmid)\)（下圖中的兩藍點）。如下圖，如果 \(f(lmid)<f(rmid)\)，則在 \([rmid,r]\)（下圖中的紅色部分）中函數必然單調遞增，最小值所在點（下圖中的綠點）必然不在這一區間內，可捨去這一區間。反之亦然。

注意

在計算 \(lmid\) 和 \(rmid\) 時，需要防止數據溢出的現象出現。

三分法每次操作會捨去兩側區間中的其中一個。為減少三分法的操作次數，應使兩側區間儘可能大。因此，每一次操作時的 \(lmid\) 和 \(rmid\) 分別取 \(mid-\varepsilon\) 和 \(mid+\varepsilon\) 是一個不錯的選擇。

實現

偽代碼

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{A range } [l,r] \text{ meaning that the domain of } f(x) \text{.} \\ 2 & \textbf{Output. } \text{The maximum value of } f(x) \text{ and the value of } x \text{ at that time } \text{.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{while } r - l > \varepsilon\\ 5 & \qquad mid\gets \frac{l+r}{2}\\ 6 & \qquad lmid\gets mid - \varepsilon \\ 7 & \qquad rmid\gets mid + \varepsilon \\ 8 & \qquad \textbf{if } f(lmid) < f(rmid) \\ 9 & \qquad \qquad r\gets mid \\ 10 & \qquad \textbf{else } \\ 11 & \qquad \qquad l\gets mid \end{array} \]

C++

1
2
3
4
5
6
7
8
9
while (r - l > eps) {
  mid = (l + r) / 2;
  lmid = mid - eps;
  rmid = mid + eps;
  if (f(lmid) < f(rmid))
    r = mid;
  else
    l = mid;
}

例題

洛谷 P3382 -【模板】三分法

給定一個 \(N\) 次函數和範圍 \([l, r]\)，求出使函數在 \([l, x]\) 上單調遞增且在 \([x, r]\) 上單調遞減的唯一的 \(x\) 的值。

解題思路

本題要求求 \(N\) 次函數在 \([l, r]\) 取最大值時自變量的值，顯然可以使用三分法。

參考代碼 
 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
27
28
29
#include <cmath>
#include <cstdio>
using namespace std;

const double eps = 0.0000001;
int N;
double l, r, A[20], mid, lmid, rmid;

double f(double x) {
  double res = (double)0;
  for (int i = N; i >= 0; i--) res += A[i] * pow(x, i);
  return res;
}

int main() {
  scanf("%d%lf%lf", &N, &l, &r);
  for (int i = N; i >= 0; i--) scanf("%lf", &A[i]);
  while (r - l > eps) {
    mid = (l + r) / 2;
    lmid = mid - eps;
    rmid = mid + eps;
    if (f(lmid) > f(rmid))
      r = mid;
    else
      l = mid;
  }
  printf("%6lf", l);
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
eps = 1e-6
n, l, r = map(float, input().split())
a = tuple(map(float, input().split()))[::-1]

def f(x):
    return sum(x ** i * j for i, j in enumerate(a))

while r - l > eps:
    mid = (l + r) / 2
    if f(mid - eps) > f(mid + eps):
        r = mid
    else:
        l = mid
print(l)

習題

分數規劃

參見：分數規劃

分數規劃通常描述為下列問題：每個物品有兩個屬性 \(c_i\)，\(d_i\)，要求通過某種方式選出若干個，使得 \(\frac{\sum{c_i}}{\sum{d_i}}\) 最大或最小。

經典的例子有最優比率環、最優比率生成樹等等。

分數規劃可以用二分法來解決。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用