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

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

本篇探討 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 例子來說,最小運輸量為 2 ,你一天一定至少要運送一個 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:
        /* bool feasibility() */

    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