Binary Search (4) 進階問題 – 陪你刷題

binary search 主題前面已經寫了三篇，建議依序看完前三篇再來看這篇。

• Binary Search (1) – 陪你刷題
• Binary Search (2) Template Overview – 陪你刷題
• Binary Search (3) template III 應用 – 陪你刷題

本篇探討 binary search 的進階題，這類問題不會直覺聯想到使用 binary search 來處理，因為這類問題的搜尋區間與目標值都不明顯，一個簡單辨識這類問題的方式為，問題存在一定的單調性(monotonic)，若 condition (k) 為 true ，則 condition (k+1), condition (k+2), ... 也為 true ，這就是一種單調性。

在前面 binary search template 中，提到 binary search 步驟 :

1. 定義搜尋區間
2. 定義 loop invariant
3. 設定區間縮減策略

但面對這類問題，還需要設計檢查可行性的 function 來檢驗是否存在單調性，這會是解這類問題的關鍵，以 Leetcode #1011 來講解這類問題。

Leetcode #1011 Capacity To Ship Packages Within D Days

這題給的 input 雖然不是有序，自然不會聯想到 binary search ，題目要求在 D 天內送完所有貨物，多份貨物將依序被分成 D 天運送，船所需的運量將等於運輸量最大的那天所載的貨物總重。

Input: weights = [2,3,3,4,3], D = 3

一天最小運輸量必定等於 input 中的最大值，一天最大運輸量一定等於所有 input 的總和，以上面 input 例子來說，單日最大運輸量為 4 ，一天至少要運送一個 package ，最大運輸量就等於貨物總重 15 ，題目問的船所需運輸量必定在這區間，對這區間做 binary search 來找在 D 天內送完時船所需最小運輸量。

除了 binary search 基本框架，需要設計檢查可行性的 function (見下方程式碼 bool feasibility)，來檢驗不同船的運輸量是否能夠順利在 D 天內送完所有貨物，變數 least_weight 作為船的運輸量，每天運送貨物重量不能超過船的運輸量，一旦超過，就需要多花一天來運輸，如果能在 D 天內送完，代表 least_weight 是可行的，可以回傳 true 。

bool feasibility (vector<int>& weights, int D,
                  int least_weight)
{
    int curr_weight = 0;
    int days = 1;
    for (int i=0; i<weights.size(); i++)
    {
        if (curr_weight + weights[i] <= least_weight)
        {
            curr_weight += weights[i];
        }
        else
        {
            curr_weight = weights[i];
            days++;
        }
    }
    if (days <= D)
    {
        return true;
    }
    else
    {
        return false;
    }
}

設計完檢查可行性的 function 後，接下來就跟之前的 binary search 沒有差別了，這類的問題困難點往往在於設計出一個可行性驗證函式。

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0;
        int right = 0;
        for (auto item:weights)
        {
            right += item;
            left = std::max (left, item);
        }

        while (left < right)
        {
            int mid = left + ((right-left)>>1);

            if (feasibility (weights, D, mid))
            {
                right = mid;
            }
            else
            {
                left = mid+1;
            }
        }
        return left;
    }
};

• 延伸問題: Leetcode #410, #774, #875, #1011, #1231, #1283, #1482

結論

這篇為 binary search 系列最後一篇文章， binary search 概念雖然簡單，但延伸出來的問題跟用法都有一定難度，如果寫這類問題時，你常常生氣於那些惱人且微小的 bug 與 edge case ，相信我，你並不孤單，這系列提供許多框架都只是用來幫助解題並更好理解 binary search 執行的過程，多練習才是王道，唯有將 binary search 問題寫過並歸類整理，才能真正深入學習 binary search 。

Reference

1. [Python] Powerful Ultimate Binary Search Template. Solved many problems-Leetcode
2. Binary Search 101 - Leetcode
3. [Java/C++/Python] Binary Search

Updated on 2023-08-13 17:15:22 星期日