$4 blog: BinarySearch

2026年3月12日星期四

從 LeetCode 3600 看工程思維：極致效能 vs 萬用架構

在面對演算法挑戰時，我們常常會陷入「尋求最快解」的迷思。然而，在真實世界的軟體工程中，最快的演算法真的永遠是最好的選擇嗎？

今天我們透過 LeetCode 3600: Maximize Spanning Tree Stability with Upgrades 這道經典的圖論題，來看看兩種截然不同的解題思路，以及它們在現實工業界中各自稱霸的真實場景。

題目背景：尋找最穩定的生成樹

這道題目的核心目標是：在給定的一張圖中，挑選出 $N-1$ 條邊形成「生成樹 (Spanning Tree)」。其中有些邊是「必選的」，有些是「可選的」。我們手上有 $K$ 次升級機會，可以將可選邊的強度乘以 2。 目標：最大化這棵樹的「最弱連結 (最小邊緣強度)」。

面對這個「最大化最小值」的難題，我們有兩種截然不同的解題策略。

策略一：二分搜尋 + 貪心驗證 (Binary Search on Answer)

這是一個非常扎實且通用的工程思維：我們不知道答案是多少，但我們可以「猜」。

運作邏輯：

確定答案的上下界（例如強度從 $0$ 到 $100,000$）。
猜測一個目標值 mid，並寫一個 check(mid) 函數來驗證：「在 $K$ 次升級內，我們能不能讓所有挑選的邊，強度都 $\ge mid$？」
根據驗證結果，不斷縮小範圍，直到找到極限值。

💡 真實世界的應用場景：高擴充性的「萬用框架」

這個演算法雖然時間複雜度多了一個 $\log M$，但在真實的工程應用中，它卻具有壓倒性的擴充性 (Extensibility)！

電信網路的 SLA 保證與預算規劃 中華電信或 AWS 要牽線連接全球的資料中心，並保證最低可用頻寬。公司今年只給了預算購買 $K$ 台「訊號放大器」。網路架構師會透過這個演算法「二分猜測」保證頻寬，驗證預算是否足夠，藉此找出基礎建設的投資報酬率極限。
EDA (電子設計自動化) 與晶片佈線 晶片設計中，工程師可以在線路上插入 Buffer（緩衝器）來增強訊號，但 Buffer 非常耗電且最多只能放 $K$ 個。軟體會猜測最差的訊號延遲時間，去驗證這 $K$ 個 Buffer 該怎麼放。
為什麼它無可取代？ 真實世界的規則往往不講武德。如果今天老闆說：「A 線路升級加 500、B 線路升級乘以 1.5、C 線路升級需要消耗 2 次升級機會...」純數學推導會瞬間崩潰，但二分搜尋版完全不受影響！你只需要在 check() 函數裡加上幾行 if-else，這個演算法就能完美存活。

策略二：Kruskal 演算法變形 (Pure Greedy)

這是一個將圖論數學性質發揮到極致的 $O(E \log E)$ 神級解法。它捨棄了「猜答案」，直接在一次遍歷中找出答案。

運作邏輯：

將所有「可選邊」依照強度由大到小排序。
依序將邊加入圖中（使用並查集 DSU 避免迴圈）。
既然有 $K$ 次升級機會，為了讓「最小值」最大化，自然要把機會留給生成樹中最弱的那 $K$ 條邊。
透過追蹤 edgesUsed，精準攔截出「沒有被升級的最弱邊」和「有被升級的最弱邊」，最後比較瓶頸即可。

💡 真實世界的應用場景：極致效能的「特製手術刀」

當規則明確且不變時，這種純貪心演算法能提供無與倫比的效能，特別適合底層系統與即時運算。

Linux Kernel 的生成樹協定 (STP) 在網路橋接系統 (net/bridge/br_stp.c) 中，為了解決交換機之間的「廣播風暴」，Kernel 必須在極短時間內找出無迴圈的生成樹。Kruskal 演算法的底層邏輯正是這類網路防護機制的核心。
機器學習：層次分群 (Hierarchical Clustering) 在資料科學中 (例如 Single-linkage Clustering)，我們需要將特徵相近的資料點分群。背後運作完全依賴排序與並查集 (DSU)，能快速將距離最短的節點合併，達成自動分類。
電腦視覺：影像分割 (Image Segmentation) 讓電腦看懂照片中哪裡是人、哪裡是背景。演算法將像素當作節點，顏色差異當作邊，透過並查集在極短的 $O(1)$ 時間內將相似區塊合併，達成即時去背效果。

總結

LeetCode 3600 教會我們最重要的一課是：演算法沒有絕對的好壞，只有最適合的情境。

如果你面對的是一個規則單純、對效能要求極高的底層系統，請拿出 Kruskal 貪心法 這把特製手術刀。
如果你面對的是一個業務邏輯複雜、需求隨時會變更的商業系統，請架構好 二分搜尋驗證 這個萬用防護罩。

下次在解題時，不妨多想一步：這段程式碼如果放到真實世界，它會扮演什麼樣的角色呢？

2025年11月17日星期一

Binary Search

今日練習的題目是 300. Longest Increasing Subsequence 主要是需要使用到 Binary Search

首先是 C++ 的 lower_bound

class Solution {
public:
    int lengthOfLIS(vector< int>& nums) {
        vector< int> arr;
        arr.reserve(nums.size());
        for (auto& num : nums) {
            auto ptr = ranges::lower_bound(arr.begin(), arr.end(), num);
            if (ptr == arr.end()) {
                arr.push_back(num);
            } else {
                *ptr = num;
            }
        }
        return arr.size();
    }
};

然後是 Python 的 bisect.bisect_left()

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = []
        for num in nums:
            i = bisect.bisect_left(arr, num)
            if i == len(arr):
                arr.append(num)
            else:
                arr[i] = num
        return len(arr)

然後是 Go 的 sort.Search()

func lengthOfLIS(nums []int) int {
	arr := make([]int, 0, len(nums))
	for _, num := range nums {
		idx := sort.Search(len(arr), func(i int) bool {
			return arr[i] >= num
		})
		if idx == len(arr) {
			arr = append(arr, num)
		} else {
			arr[idx] = num
		}
	}
	return len(arr)
}

最後是 Rust 的 binary_search

impl Solution {
    pub fn length_of_lis(nums: Vec< i32>) -> i32 {
        let mut arr = Vec::with_capacity(nums.len());
        for num in nums {
            let i = match arr.binary_search(&num) {
                Ok(index) => index,
                Err(index) => index,
            };
            if i == arr.len() {
                arr.push(num);
            } else {
                arr[i] = num;
            }
        }
        arr.len() as i32
    }
}

每種程式語言使用方式都有所不同。

網頁

2026年3月12日 星期四