在算法學習中，二分答案算法是一種非常高效且常用的技巧。它的核心思想是通過不斷縮小搜索范圍，逐步逼近目標答案。相比傳統的暴力搜索，二分答案算法的時間復雜度通常為 O(logn)，特別適合處理大規模數據的查找問題。

本文將詳細介紹二分答案算法的兩種常見模板，并結合實際應用場景，幫助你更好地理解和使用這一算法。

二分答案算法的基本原理

二分答案算法的核心思想是：在一個有序的區間中，通過不斷將區間分成兩部分，判斷答案可能存在的那一部分，從而逐步縮小搜索范圍，最終找到目標答案。

這種算法特別適合以下幾種場景：

1. 尋找符合要求的區間的最大值或最小值：例如，找到一個數組中第一個滿足條件的元素。

2. 尋找最大值的最小值：例如，在分配問題中找到最小的最大分配值。

3. 尋找最小值的最大值：例如，在優化問題中找到最大的最小值。

這些場景通常難以通過傳統的暴力搜索高效解決，而二分答案算法可以輕松應對。

二分答案算法的適用場景

在實際編程中，二分答案算法的應用非常廣泛。以下是一些常見的適用場景：

1. 尋找符合要求的區間的邊界：

   • 例如，找到一個有序數組中第一個大于等于某個值的元素。

   • 或者找到最后一個小于等于某個值的元素。

2. 優化問題中的極值查找：

   • 例如，在分配問題中，找到最小的最大分配值。

   • 或者在調度問題中，找到最大的最小時間間隔。

3. 尋找滿足條件的最優解：

   • 例如，在矩陣中找到滿足條件的最小元素。

二分答案算法的兩種模板

模板一：查找左邊界和右邊界

查找左邊界 (Search Left, SL)

int SL(int l, int r) {while (l < r) {int mid = l + r >> 1; // 等價于 (l + r) / 2if (check(mid)) r = mid;else l = mid + 1;}return l;
}

查找右邊界 (Search Right, SR)

int SR(int l, int r) {while (l < r) {int mid = l + r + 1 >> 1; // 需要 +1 防止死循環if (check(mid)) l = mid;else r = mid - 1;}return r;
}

模板一的特點

1. 查找左邊界：

   • mid 的計算方式為 (l + r) / 2。

   • 如果 check(mid) 為真，則說明目標可能在左半部分，將右邊界 r 更新為 mid。

   • 否則，將左邊界 l 更新為 mid + 1。

2. 查找右邊界：

   • mid 的計算方式為 (l + r + 1) / 2，這是為了避免死循環。

   • 如果 check(mid) 為真，則說明目標可能在右半部分，將左邊界 l 更新為 mid。

   • 否則，將右邊界 r 更新為 mid - 1。

模板二：另一種實現方式

查找左邊界 (Search Left, SL)

int SL(int l, int r) {while(l <= r) {int mid = (l + r) >> 1;if(check(mid)) {r = mid - 1; // 繼續在左半部分查找} else {l = mid + 1; // 繼續在右半部分查找}}return l;
}

查找右邊界 (Search Right, SR)

int SR(int l, int r) {while(l <= r) {int mid = (l + r) >> 1;if(check(mid)) {l = mid + 1; // 繼續在右半部分查找} else {r = mid - 1; // 繼續在左半部分查找}}return r;
}

模板二的特點

1. 查找左邊界：

   • 如果 check(mid) 為真，則說明目標可能在左半部分，將右邊界 r 更新為 mid - 1。

   • 否則，將左邊界 l 更新為 mid + 1。

   • 最終返回 l，即左邊界。

2. 查找右邊界：

   • 如果 check(mid) 為真，則說明目標可能在右半部分，將左邊界 l 更新為 mid + 1。

   • 否則，將右邊界 r 更新為 mid - 1。

   • 最終返回 r，即右邊界。

模板對比與適用場景

模板一的優點

• 代碼更簡潔：邏輯清晰，適合快速實現。

• 適用于精確查找邊界：特別適合需要找到第一個滿足條件的元素（左邊界）或最后一個滿足條件的元素（右邊界）。

模板二的優點

• 更統一：求mid的時候，不用分+1的情況

• 更直觀：容易理解，適合初學者。

• 適用于范圍查找：適合需要找到滿足條件的元素范圍的邊界。

選擇模板的建議

• 如果你需要快速實現并確保代碼簡潔，可以選擇模板一。

• 如果你需要更直觀的邏輯處理和更統一的模板，可以選擇模板二。

模版的記憶方法

求左邊界則返回L，求右邊界則返回R

二分答案算法的實際應用

在實際編程中，二分答案算法的應用非常廣泛。以下是一些常見的應用場景和示例：

示例 1：尋找符合要求的區間的最小值

假設你需要在一個有序數組中找到第一個大于等于某個目標值的元素。可以使用模板一的查找左邊界方法。

bool check(int mid, int target, vector<int>& arr) {return arr[mid] >= target;
}int findFirstGreaterEqual(int target, vector<int>& arr) {int l = 0, r = arr.size() - 1;return SL(l, r);
}

示例 2：尋找最大值的最小值

例如，在分配問題中，你需要將一組物品分配給若干人，使得每個人分配到的物品總和的最大值最小。可以使用二分答案算法來尋找這個最小的最大值。

bool check(int mid, vector<int>& items, int k) {int cnt = 1, sum = 0;for (int item : items) {sum += item;if (sum > mid) {cnt++;sum = item;}}return cnt <= k;
}int findMinMaxAllocation(vector<int>& items, int k) {int l = *max_element(items.begin(), items.end());int r = accumulate(items.begin(), items.end(), 0);return SL(l, r);
}

示例 3：尋找最小值的最大值

例如，在調度問題中，你需要找到最大的最小時間間隔。可以使用二分答案算法來尋找這個最大的最小值。

bool check(int mid, vector<int>& times) {int cnt = 1, prev = times[0];for (int time : times) {if (time - prev >= mid) {cnt++;prev = time;}}return cnt >= required;
}int findMaxMinInterval(vector<int>& times, int required) {sort(times.begin(), times.end());int l = 0, r = times.back() - times[0];return SR(l, r);
}

總結

二分答案算法是一種非常強大的工具，特別適合解決以下幾類問題：

1. 尋找符合要求的區間的最大值或最小值。

2. 尋找最大值的最小值。

3. 尋找最小值的最大值。

通過本文介紹的兩種模板，你可以根據具體問題選擇合適的實現方式。模板一適合快速實現精確查找，而模板二則更適合處理復雜的邊界條件。

希望本文能幫助你更好地理解和使用二分答案算法！如果你有任何問題或建議，歡迎在評論區留言。讓我們一起探索算法的無限可能！