Binary Search - 二分搜索

二分搜索是一種在有序陣列中尋找目標值的經典方法，也就是說使用前提是『有序陣列』。非常簡單的題中『有序』特徵非常明顯，但更多時候可能需要我們自己去構造『有序陣列』。下面我們從最基本的二分搜索開始逐步深入。

模板一 - lower/upper bound

定義 lower bound 爲在給定升序陣列中大於等於目標值的最小索引，upper bound 則爲小於等於目標值的最大索引，下面給出程式碼和測試用例。

Java

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         int[] nums = new int[]{1,2,2,3,4,6,6,6,13,18};
  6.         System.out.println(lowerBound(nums, 6)); // 5
  7.         System.out.println(upperBound(nums, 6)); // 7
  8.         System.out.println(lowerBound(nums, 7)); // 8
  9.         System.out.println(upperBound(nums, 7)); // 7
  10.     }
  12.     /*
  13.     * nums[index] >= target, min(index)
  14.     */
  15.     public static int lowerBound(int[] nums, int target) {
  16.         if (nums == null || nums.length == 0) return -1;
  17.         int lb = -1, ub = nums.length;
  18.         while (lb + 1 < ub) {
  19.             int mid = lb + (ub - lb) / 2;
  20.             if (nums[mid] < target) {
  21.                 lb = mid;
  22.             } else {
  23.                 ub = mid;
  24.             }
  25.         }
  27.         return lb + 1;
  28.     }
  30.     /*
  31.     * nums[index] <= target, max(index)
  32.     */
  33.     public static int upperBound(int[] nums, int target) {
  34.         if (nums == null || nums.length == 0) return -1;
  35.         int lb = -1, ub = nums.length;
  36.         while (lb + 1 < ub) {
  37.             int mid = lb + (ub - lb) / 2;
  38.             if (nums[mid] > target) {
  39.                 ub = mid;
  40.             } else {
  41.                 lb = mid;
  42.             }
  43.         }
  45.         return ub - 1;
  46.     }
  47. }

源碼分析

以lowerBound的實現爲例，以上二分搜索的模板有幾個非常優雅的實現：

  1. while 循環中 lb + 1 < ub, 而不是等號，因爲取等號可能會引起死循環。初始化lb < ub 時，最後循環退出時一定有lb + 1 == ub.
  2. mid = lb + (ub - lb) / 2, 可有效防止兩數相加後溢出。
  3. lb 和 ub 的初始化，初始化爲陣列的兩端以外，這種初始化方式比起0 和nums.length - 1 有不少優點，詳述如下。

如果遇到有問插入索引的位置時，可以分三種典型情況：

  1. 目標值在陣列範圍之內，最後返回值一定是lb + 1
  2. 目標值比陣列最小值還小，此時lb 一直爲-1, 故最後返回lb + 1 也沒錯，也可以將-1 理解爲陣列前一個更小的值
  3. 目標值大於等於陣列最後一個值，由於循環退出條件爲lb + 1 == ub, 那麼循環退出時一定有lb = A.length - 1, 應該返回lb + 1

綜上所述，返回lb + 1是非常優雅的實現。其實以上三種情況都可以統一爲一種方式來理解，即索引-1 對應於陣列前方一個非常小的數，索引ub 即對應陣列後方一個非常大的數，那麼要插入的數就一定在lb 和ub 之間了。

有時複雜的邊界條件處理可以通過『補項』這種優雅的方式巧妙處理。

關於lb 和 ub 的初始化，由於mid = lb + (ub - lb) / 2, 且有lb + 1 < ub，故 mid 還是有可能爲ub - 1或者lb + 1的，在需要訪問mid + 1或者mid - 1處索引的元素時可能會越界。這時候就需要將初始化方式改爲lb = 0, ub = A.length - 1 了，最後再加一個關於lb, ub 處索引元素的判斷即可。如 Search for a Range 和 Find Peak Element. 尤其是 Find Peak Element 中 lb 和 ub 的初始值如果初始化爲-1和陣列長度會帶來一些麻煩。

模板二 - 最優解

除了在有序陣列中尋找目標值這種非常直接的二分搜索外，我們還可以利用二分搜索求最優解（最大值/最小值），通常這種題中只是隱含了『有序陣列』，需要我們自己構造。

用數學語言來描述就是『求滿足某條件 C(x) 的最小/大的 x』，以求最小值爲例，對於任意滿足條件的 x, 如果所有的 x \leq x^\prime \leq UB 對於 C(x^\prime) 都爲真（其中 UB 可能爲無窮大，也可能爲滿足條件的最大的解，如果不滿足此條件就不能保證二分搜索的正確性），那麼我們就能使用二分搜索進行求解，其中初始化時下界lb 初始化爲不滿足條件的值LB, 上界初始化爲滿足條件的上界UB. 隨後在while 循環內部每次取中，滿足條件就取ub = mid, 否則lb = mid, 那麼最後ub 就是要求的最小值。求最大值時類似，只不過處理的是lb.

以 POJ No.1064 爲例。

Problem Statement

有 N 條繩子，它們的長度分別爲 L_i. 如果從它們中切割出 K 條長度相同的繩子的話，這 K 條繩子每條最長能有多長？答案保留到小數點後兩位。

輸入

  1. N = 4, L = {8.02, 7.43, 4.57, 5.39}, K = 11

輸出

2.00

題解

這道題看似是一個最優化問題，我們來嘗試下使用模板二的思想求解，令 C(x) 爲『可以得到 K 條長度爲 x 的繩子』。根據題意，我們可以將上述條件進一步細化爲：

C(x) = \sum_i(floor(L_i / x)) \geq K

我們現在來分析下可行解的上下界。由於答案保留小數點後兩位，顯然繩子長度一定大於0，大於0的小數點後保留兩位的最小值爲0.01, 顯然如果問題最後有解，0.01 一定是可行解中最小的，且這個解可以分割出的繩子條數是最多的。一般在 OJ 上不同變量都是會給出範圍限制，那麼我們將上界初始化爲最大範圍 + 0.01, 它一定在可行解之外（也可以遍歷一遍陣列取陣列最大值，但其實二分後複雜度相差不大）。使用二分搜索後最後返回lb 即可。

Java

  1. import java.io.*;
  2. import java.util.*;
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner in = new Scanner(System.in);
  7.         int n = in.nextInt();
  8.         int k = in.nextInt();
  9.         double[] nums = new double[n];
  10.         for (int i = 0; i < n; i++) {
  11.             nums[i] = in.nextDouble();
  12.         }
  13.         System.out.printf("%.2f\n", Math.floor(solve(nums, k) * 100) / 100);
  14.     }
  16.     public static double solve(double[] nums, int K) {
  17.         double lb = 0.00, ub = 10e5 + 0.01;
  18.         // while (lb + 0.001 < ub) {
  19.     for (int i = 0; i < 100; i++) {
  20.             double mid = lb + (ub - lb) / 2;
  21.             if (C(nums, mid, K)) {
  22.                 lb = mid;
  23.             } else {
  24.                 ub = mid;
  25.             }
  26.         }
  27.         return lb;
  28.     }
  30.     public static boolean C(double[] nums, double seg, int k) {
  31.         int count = 0;
  32.         for (double num : nums) {
  33.             count += Math.floor(num / seg);
  34.         }
  35.         return count >= k;
  36.     }
  37. }

源碼分析

方法C 只做一件事，給定陣列nums, 判斷是否能切割出K 條長度均爲seg 的繩子。while 循環中使用lb + 0.001 < ub, 不能使用0.01, 因爲計算mid 時有均值的計算，對於double 型數值否則會有較大誤差。

模板三 - 二分搜索的 while 結束條件判定

對於整型我們通常使用lb + 1 < ub, 但對於double型數據來說會有些精度上的丟失，使得結束條件不是那麼好確定。像上題中採用的方法是題目中使用的精度除10。但有時候這種精度可能還是不夠，如果結束條件lb + EPS < ub中使用的 EPS 過小時 double 型數據精度有可能不夠從而導致死循環的產生！這時候我們將while循環體替換爲for (int i = 0; i < 100; i++), 100 次循環後可以達到 10^{-30} 精度範圍，一般都沒問題。

模板四 － （九章算法）模版

這個模版跟第一個模版類似， 但是相對更容易上手。這個模版的核心是， 將binary search 問題轉化成：尋找第一個或者最後一個，該target元素出現的位置的問題，Find the any/first/last position of target in nums. 詳解請見下面的例題。這個模版有四個要素。

  1. start + 1 < end
    表示， 當指針指到兩個元素，相鄰或者相交的時候， 循環停止。 這樣的話在最終分情況討論的時候，只用考慮1～2個元素。
  2. start + (end - start) / 2
    寫C++ 和 Java的同學要考慮到int overflow的問題， 所以需要考慮邊界情況。 寫Python的同學就不用考慮了， 因爲python這個語言本身已經非常努力的保證了number不會overflow。
  3. A[mid] ==, >, <
    在循環中， 分三種情況討論邊界。 要注意， 在移動start和end的時候， 只要單純的把指針指向mid的位置， 不要+1或者-1。 因爲只移動邊界到mid的位置， 不會誤刪除target。在工程中，儘量在程序最後的時候統一寫return, 這樣可以增強可讀性。
  4. A[start], A[end]? target
    在循環結束時，因爲只有1～2個元素需要討論，所以結果非常容易解釋清楚。 只存在的2種情況爲， 1. start + 1 == end 邊界指向相鄰的兩個元素， 這時只需要分情況討論start和end與target的關係，就可以得出結果。 2. start == end 邊界指向同一元素， 其實這個情況還是可以按照1的方法，分成start``end討論，只不過討論結果一樣而已。

Python

  1. class Solution:
  2.     def binary_search(self, array, target):
  3.         if not array:
  4.             return -1
  6.         start, end = 0, len(array) - 1
  7.         while start + 1 < end:
  8.             mid = (start + end) / 2
  9.             if array[mid] == target:
  10.                 start = mid
  11.             elif array[mid] < target:
  12.                 start = mid
  13.             else:
  14.                 end = mid
  16.         if array[start] == target:
  17.             return start
  18.         if array[end] == target:
  19.             return end
  20.         return -1

Java

  1. class Solution {
  2.     public int binarySearch(int[] array, int target) {
  3.         if (array == null || array.length == 0) {
  4.             return -1;
  5.         }
  7.         int start = 0, end = array.length - 1;
  8.         while (start + 1 < end) {
  9.             int mid = start + (end - start) / 2;
  10.             if (array[mid] == target) {
  11.                 start = mid;
  12.             } else if (array[mid] < target) {
  13.                 start = mid;
  14.             } else {
  15.                 end = mid;
  16.             }
  17.         }
  18.         if (array[start] == target) {
  19.             return start;
  20.         }
  21.         if (array[end] == target) {
  22.             return end;
  23.         }
  24.         return -1;
  25.     }
  26. }

Problem Statement

Search for a Range

樣例

給出[5, 7, 7, 8, 8, 10]和目標值target=8,

返回[3, 4]

Python

  1. class Solution:
  2.     def search_range(self, array, target):
  3.         ret = [-1, -1]
  4.         if not array:
  5.             return ret
  6.         # search first position of target
  7.         st, ed = 0, len(array) - 1
  8.         while st + 1 < ed:
  9.             mid = (st + ed) / 2
  10.             if array[mid] == target:
  11.                 ed = mid
  12.             elif array[mid] < target:
  13.                 st = mid
  14.             else:
  15.                 ed = mid
  16.         if array[st] == target:
  17.             ret[0] = st
  18.         elif array[ed] == target:
  19.             ret[0] = ed
  21.         # search last position of target
  22.         st, ed = 0, len(array) - 1
  23.         while st + 1 < ed:
  24.             mid = (st + ed) / 2
  25.             if array[mid] == target:
  26.                 st = mid
  27.             elif array[mid] < target:
  28.                 st = mid
  29.             else:
  30.                 ed = mid
  31.         if array[ed] == target:
  32.             ret[1] = ed
  33.         elif array[st] == target:
  34.             ret[1] = st
  36.         return ret

源碼分析

search range的問題可以理解爲， 尋找第一次target出現的位置和最後一次target出現的位置。 當尋找第一次target出現位置的循環中， array[mid] == target表示， target可以出現在mid或者mid更前的位置， 所以將ed移動到mid。當循環跳出時， st的位置在ed之前，所以先判斷在st位置上是否是target， 再判斷ed位置。當尋找最後一次target出現位置的循環中，array[mid] == target表示， target可以出現在mid或者mid之後的位置， 所以將st移動到mid。 當循環結束時，ed的位置比st的位置更靠後， 所以先判斷ed的位置是否爲target， 再判斷st位置。 最後返回ret。

Reference

  • 《挑戰程序設計競賽》