「二分」有關，算是非常普遍與重要的知識點。然而有很多同學依然沒能很好地掌握，總是會在各種細節上跌跟頭，因此今天我們將對二分算法進行系統地梳理。

「二分」一共有三類常見應用，分別是「整數二分」、「實數二分」以及「二分答案」，接下來將分別介紹這三類應用的具體形式。

一、整數二分

整數二分即為在整數集合上的二分，常見的用法有：在單調序列中查找「某個數是否出現過」、「某個數最早出現的位置」以及「>= 某個數中最小的數」等。

解決這類問題的思想非常統一，即對坐標區間不斷進行折半，以此在 O(log(n)) 的時間復雜度內確定答案，但其「實現方法」卻非常多樣，由此導致很多同學在此類問題上出錯。

因此接下來將通過一個例題來介紹「記錄 ans」的二分實現方法，該方法較易理解且不易出錯。

34. 在排序數組中查找元素的第一個和最后一個位置

題目描述

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置，如果數組中不存在目標值 target，返回 [-1, -1]。設計并實現時間復雜度為 O(log(n)) 的算法解決此問題。

示例 1

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例 2

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3

輸入：nums = [], target = 0
輸出：[-1,-1]

提示

• 0 <= nums.length <= 1e5
• -1e9 <= nums[i] <= 1e9
• nums 是一個非遞減數組
• -1e9 <= target <= 1e9

 

題目講解

我們以數組 nums = [3 4 4 4 6], target = 4 進行舉例，首先是確定 4 的開始位置，具體代碼如下：

int l = 0, r = 4, ans = 0;
while (l <= r) {
    int mid = (l + r) / 2;
    if (nums[mid] >= target) {
        ans = mid;
        r = mid - 1;
    }
    else l = mid + 1;
}
if (nums[ans] != target) ans = -1;

上述代碼在二分過程中，[l, r] 始終代表二分搜索的區間，而 ans 則代表「數組中第一個 >= target」的位置。最后再通過判斷 nums[ans] 是否等于 target 來確定 target 是否存在于數組中。

我們來模擬一下這個過程，首先二分搜索區間為 [0, 4]，因此 mid = 2。此時 nums[2] >= 4，即 2 可能是「數組中第一個 >= target」的位置，因此更新 ans 為 2。

 

又因為 nums[mid] >= 4，即答案一定不在右半區間，即 [3, 4]，于是令 r = mid - 1，搜索區間變為 [0, 1]。此時 mid = 0，nums[0] < target，因此 mid 無法更新 ans。

 

由于 nums[mid] < target，因此答案一定不在左半區間，于是 l = mid + 1，搜索區間變為 [1, 1]。此時 mid = 1，nums[1] >= target，更新 ans = 1。

 

由于 nums[mid] >= target，于是 r = mid - 1，不再滿足 l <= r 的條件，二分過程結束。最終 ans = 1，二分成功。

通過上述這個過程，我們可以總結出「整數二分」的實現規律，首先由 while (l <= r) 來控制二分進程，每次計算 mid = (l + r) / 2，并判斷 mid 是否為可能的答案。如果是，則更新 ans，否則不更新。另外根據 mid 判斷接下來是搜索左半區間 [l, mid - 1]，還是右半區間 [mid + 1, r]，不斷循環。退出循環后，ans 即為要求的答案。

根據上述示例，大家可以自行完成「查找 target 結束位置」的代碼，并查看下述完整代碼進行驗證。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1, ans1 = 0, ans2 = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                ans1 = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] <= target) {
                ans2 = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if (nums.size() && nums[ans1] == target) return {ans1, ans2};
        else return {-1, -1};
    }
};

二、實數二分

實數二分即為實數域上的二分，即二分搜索區間 [l, r] 從整數變為了實數。對比整數二分，實數二分的算法思想沒有變化，唯一變化的只有二分實現方法。

通常來說實數二分有兩種實現方法，第一種是通過確定好的精度 eps（如 1e-6、1e-8 等），以 l + eps < r 為循環條件，每次根據在 mid 上的判定，選擇左半區間 [l, mid] 或右半區間 [mid, r]。循環結束后，l 即為最終答案，代碼示例如下：

while (l + 1e-6 < r) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

有時精度不容易確定，因此直接固定循環次數進行二分，即第二種方法。與第一種方法僅有「循環條件」的區別，代碼示例如下：

for (int i = 0; i < 100; i++) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

三、二分答案

二分算法成立的關鍵在于單調性，因此任何具有單調性的問題，我們都可以考慮在其上使用二分算法的可能性。正是基于這一點，當問題的答案具有單調性時，我們可以通過二分將「問題的求解」轉化為「問題的判定」，該方法即為「二分答案」。

接下來我們將通過兩道例題進一步地講解該算法。

287. 尋找重復數

題目描述

給定一個包含 n + 1 個整數的數組 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數。

假設 nums 只有一個重復的整數，請找出這個重復的數，并只使用 O(1) 的額外空間。

 

示例 1

輸入：nums = [1,3,4,2,2]
輸出：2

示例 2

輸入：nums = [3,1,3,4,2]
輸出：3

示例 3

輸入：nums = [1,1]
輸出：1

示例 4

輸入：nums = [1,1,2]
輸出：1

提示

• 2 <= n <= 3e4
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中只有一個整數出現兩次或多次，其余整數均只出現一次

題目講解

本題有很多種做法，但我們主要以該題為例來講解「二分答案」，因此我們直接進入「二分答案」的思考過程。

一道題想要使用「二分答案」，其最大的前提是「答案有單調性」，而本題所求解的答案是顯然的，即「重復數的值」。所以我們需要找到一個「判定條件」，使得對于二分區間 [l, r]，我們可以根據其中值 mid 是否滿足「判定條件」，來確定下一個搜索區間是左半部分還是右半部分。

在本題中，我們令 f(x) 表示數組中 <= x 的個數，則不難發現 f(x) 是關于 x 的單調函數，即隨著 x 的變大，f(x) 要么變大要么不變。

具體來說，假設重復數為 A，則對于所有小于 A 的數 x，f(x) = x；而所有大于等于 A 的數 y，f(y) > y。例如對于數組 [1 2 2 2 3]，n = 4，f(1) = 1，f(2) = 4，f(3) = 5，f(4) = 5。

由此我們可以通過「二分答案」來解決本題，對于二分區間 [l, r]，其中值為 mid，若 f(mid) > mid，則說明重復數小于等于 mid，因此更新 ans = mid，且將二分區間變為 [l, mid - 1]；否則不更新 ans 且二分區間變為 [mid + 1, r]。

二分答案的時間復雜度為 O(log(n))，對于特定的 mid，求解 f(mid) 的時間復雜度為 O(n)，因此本題總的時間復雜度為 O(nlog(n))，具體代碼如下所示：

class Solution {
public:
    bool check(vector<int>& nums, int mid) {
        int cnt = 0;
        for (int x:nums) {
            if (x <= mid) cnt++;
        }
        if (cnt > mid) return 1;
        else return 0;
    }
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size(), ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(nums, mid)) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans;
    }
};

其中 while 循環中的 check 函數即為「二分答案」問題中的「判定條件」。對于「二分答案」所適用的題目，我們通常只需對 check 函數進行修改，while 循環中的部分基本不變。

 

410. 分割數組的最大值

題目描述

給定一個非負整數數組 nums 和一個整數 m，你需要將這個數組分成 m 個非空的連續子數組。

設計一個算法使得這 m 個子數組各自和的最大值最小。

示例 1

輸入：nums = [7,2,5,10,8], m = 2
輸出：18
解釋：
一共有四種方法將 nums 分割為 2 個子數組。其中最好的方式是將其分為 [7,2,5] 和 [10,8] 。
因為此時這兩個子數組各自的和的最大值為18，在所有情況中最小。

示例 2

輸入：nums = [1,2,3,4,5], m = 2
輸出：9

示例 3

輸入：nums = [1,4,4], m = 3
輸出：4

提示

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1e6
• 1 <= m <= min(50, nums.length)

題目講解

查看題干，「最大值最小」，這是答案具有單調性，可用二分將「問題求解」轉換為「問題判定」最常見、最典型的特征之一。

具體來說，在本題中，若「子數組和的最大值小于等于 x」符合數組分割要求，則比 x 更大的答案也一定符合要求。即當 x 為負數時，數組分割要求無法滿足，但隨著 x 的不斷變大，會有一個分界點 A，當 x 大于等于 A 時，數組分割要求即可滿足，而這個 A 即為本題答案。

由此本題從「求解 A」轉換為了「二分 A 并判斷數組分割要求是否可以滿足」。對于二分區間 [l, r]，其中值為 mid，若 mid 滿足數組分割要求，則更新 ans = mid，二分區間變為 [l, mid - 1]；否則不更新 ans 且二分區間變為 [mid + 1, r]。

所以本題的「判定條件」為：對于特定的 mid，判斷當子數組和的最大值 <= mid 時，子數組是否可以分成 m 個非空的連續子數組。

對于該「判定條件」，我們可以使用貪心算法，從前往后遍歷數組，用 sum 表示當前分割子數組的和，cnt 表示已經分割出的子數組的數量。若 sum 加上當前值 nums[i] 大于 x，則將 cnt 加 1，并將當前值作為新的一段分割子數組的開頭，即 sum = nums[i]。遍歷結束后，若 cnt <= m，則判定條件可以滿足，否則無法滿足。

由此本題得以解決，具體代碼如下所示：

class Solution {
public:
    bool check(vector<int>& nums, int m, int mid) {
        int len = nums.size(), sum = 0, cnt = 1;
        for (int x:nums) {
            if (x > mid) return 0;
            if (sum + x <= mid) sum += x;
            else sum = x, cnt++;
        }
        return cnt <= m;
    }
    int splitArray(vector<int>& nums, int m) {
        int l = 0, r = 1e9, ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(nums, m, mid)) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans;
    }
};

總結一下，當問題的答案具有單調性時，我們可以通過「二分答案」將「問題的求解」轉換為「問題的判定」，進而完成解題的過程。

四、綜合練習

最后我們以一道經典二分題為例進行綜合練習，該題目難度較大，也是一道經典的面試題，希望大家能好好理解并掌握。

4. 尋找兩個正序數組的中位數

題目描述

給定兩個大小為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并返回這兩個正序數組的中位數，且時間復雜度不高于 O(log (m+n))。

示例 1

輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數組 = [1,2,3] ，中位數 2

示例 2

輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數組 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5

示例 3

輸入：nums1 = [0,0], nums2 = [0,0]
輸出：0.00000

示例 4

輸入：nums1 = [], nums2 = [1]
輸出：1.00000

示例 5

輸入：nums1 = [2], nums2 = []
輸出：2.00000

提示

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -1e6 <= nums1[i], nums2[i] <= 1e6

題目講解

首先考慮一下本題能否「二分答案」，由于奇數長度與偶數長度解法類似，因此僅考慮 m + n 為奇數時的情況。

當 m + n 為奇數時，中位數即為兩個數組排序后第 (m + n + 1) / 2 個數，因此令 f(x) 表示兩個數組中 <= x 的數的個數，中位數即為滿足 f(x) >= (m + n + 1) / 2 中最小的 x。由于兩個數組均為正序，因此對于一個特定的 x，我們可以通過兩次二分在 O(log(n) + log(m)) 的時間復雜度內求得 f(x)。

由此我們可以得知「二分答案」的時間復雜度為 O(log(2e6)(log(n)+log(m)))，其中 2e6 為「二分答案」初始區間 [-1e6, 1e6] 的長度。因此「二分答案」無法達到「時間復雜度不高于 O(log (m+n))」的要求，我們需要轉換思路。

重新思考中位數的作用，我們可以發現：中位數常用于將一個序列劃分為長度最多相差 1 的兩部分，且其中一部分的元素始終大于等于另一部分。

為了便于表述，將 nums1 和 nums2 數組分別記為 A 和 B。接下來模擬序列的劃分過程，在 A 數組中選取前 i 個數（A[0], A[1], ..., A[i-1]），在 B 數組中選取前 j 個數（B[0], B[1], ..., B[j-1]）。這 i + j 個數組成第一部分，剩下的 n + m - i - j 個數為第二部分。

進一步地，當 m + n 為偶數時，兩部分長度一致，且第一部分最大值小于等于第二部分最小值，即：

 

此時中位數等于

 

；當 m + n 為奇數時，我們規定第一部分長度比第二部分大 1，且兩部分的最值關系依然滿足，即：

 

此時中位數等于

 

。觀察上述兩個式子，發現無論 m + n 為奇還是偶，均滿足

 

。因此為了便于計算，我們將

 

與

 

統一為

 

（此處為整除）。

又因為 A、B 均為升序數組，因此上述兩個式子可以修改為：

 

繼續觀察可以發現，當 i 增大時，j 在減小，即隨著 i 的增加，A[i-1] 不斷增加，而 B[j] 則不斷減小。因此一定存在一個臨界點 (i, j) 滿足 A[i-1] ≤ B[j] ，而 i 再增加 1 則不再滿足，即：

 

不難發現，臨界點 (i, j) 剛好滿足 i、j 劃分數組的要求，因此本題可以通過二分 i 的位置，尋找最大的滿足 A[i-1] ≤ B[j] 的 i，即可完成數組劃分并求得中位數。

另外需要注意 i、j 可能會超出數組范圍，因此規定 A[-1] = B[-1] = -1e9，A[m] = B[n] = 1e9。由此本題得以解決，時間復雜度為 O(log(min(m, n)))，滿足題目要求。

代碼實現

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) swap(nums1, nums2);
        int n = nums1.size(), m = nums2.size(), l = 0, r = n, ans = 0;
        while (l <= r) {
            int i = (l + r) / 2, j = (n + m + 1) / 2 - i;
            if (i <= 0 || j >= m || nums1[i-1] <= nums2[j]) {
                ans = i;
                l = i + 1;
            }
            else r = i - 1;
        }
        int i = ans, j = (n + m + 1) / 2 - i, x1 = -1e9, x2 = -1e9, x3 = 1e9, x4 = 1e9;
        if (i > 0) x1 = nums1[i-1];
        if (j > 0) x2 = nums2[j-1];
        if (i < n) x3 = nums1[i];
        if (j < m) x4 = nums2[j];
        if ((n + m) % 2) return max(x1, x2);
        else return (max(x1, x2) + min(x3, x4)) / 2.0;
    }
};

總結

二分是一個非常常見卻又極其精妙的算法，經常成為解題的一個突破口。該算法一共有三類常見應用，即「整數二分」、「實數二分」以及「二分答案」，其中「二分答案」能將「問題的求解」轉換為「問題的判定」，因此應用非常廣泛。

二分并沒有固定的模板與套路，靈活性非常高，因此我們需要深刻理解其算法思想，并加以習題來鞏固，以期早日掌握。

 

本文作者：Gene_Liu

聲明：本文歸 “力扣” 版權所有，如需轉載請聯系。文中部分圖片來源于網絡，如有侵權聯系刪除。