二分搜尋題型與題解 (Binary Search Problems)

本章節專注於二分搜尋法的進階應用與實戰演練。除了基礎的查找外，我們將學習如何對「答案」進行二分搜，解決最大化最小值、第 k 大元素等經典競賽題型。

1. 極值問題

#

介紹如何在單峰函數或特定區間內，利用二分搜尋快速找到最大值或最小值。

2. 第 k 大問題

#

針對「尋找第 k 大/小數值」的類型，解析如何對數值範圍進行二分搜來反推答案。

3. 題解：Get together

#

Codeforces 題目解析：在數線上尋找所有人集合所需的最短時間。

4. 題解：Splitting an Array

#

經典題型解析：將陣列切割成 k 段，使得各段總和的最大值盡可能小。

5. 題解：Cows in Stalls

#

經典題型解析：在牛棚中安排牛隻位置，使得牛隻之間的最小距離盡可能大（最大化最小值）。

6. 題解：Minimum maximum on the Path

#

圖論結合二分搜：在圖上尋找一條路徑，使其經過邊的最大權重最小化。

7. 題解：K-th Number in the Union of Segments

#

進階題型：在多個區間聯集中尋找第 k 小的數字。

8. 題解：Multiplication Table

#

進階題型：在 \(N \times N\) 的乘法表中尋找第 k 小的數值。

9. 題解：K-th Sum

#

進階題型：給定兩個陣列，求所有可能配對總和中第 k 小的和。