1. 項目概述從“三分”到“凸函數”的精確求解在算法競賽和許多工程優化問題中我們常常會遇到一類特殊的函數它們只有一個“谷底”或“峰頂”。想象一下你在山里找最低點或者在海面上找最高點你不需要走遍每一寸土地只需要用一種高效的策略逐步縮小搜索范圍。這就是“三分法”要解決的核心問題。它不是一個簡單的數值方法而是一個基于函數凸凹性質的確定性搜索算法專門用于在連續區間上尋找單峰函數的極值點。我最初接觸它是在解決一些最優路徑、資源分配和參數調優的問題時發現暴力枚舉效率低下而導數法又因為函數形式復雜或不可導而無法應用。三分法以其簡潔的思想和穩定的性能成為了我工具箱里的?？?。所謂“三分”顧名思義就是將當前的搜索區間等分成三份通過比較兩個中間分界點的函數值來果斷地舍棄掉不可能包含最值的那三分之一區間。這個過程反復迭代區間迅速縮小直到滿足我們的精度要求。它解決的是這樣一個明確的需求給定一個在區間[l, r]上先嚴格單調增、后嚴格單調減或先減后增的函數f(x)找到那個讓f(x)取得最大值或最小值的x。這個“單峰”的性質就是“凸函數”在此語境下的實際含義更嚴格地說用于找最小值的是凸函數找最大值的是凹函數。本文將為你徹底拆解這個算法的原理、實現細節、各種變體以及實戰中那些教科書上不會講的坑。無論你是正在備賽的選手還是遇到類似優化問題的工程師這份“凸函數模板”的深度解析都能讓你不僅會套用更能理解其筋骨靈活應用于各種場景。2. 算法核心原理與思路拆解2.1 為什么是“三分”—— 與二分法的本質區別很多人熟悉二分法它用于在單調序列中查找目標值。三分法可以看作是二分法在尋找函數極值問題上的一個類比和擴展。但它們有一個根本性的不同二分法依賴于區間的單調性而三分法依賴于區間的單峰性。二分法每次比較中點值與目標值的關系總能舍棄一半區間因為它明確知道目標在中點的左邊還是右邊。但對于一個單峰函數你只知道極值點在某處比較一個點的函數值無法告訴你極值點在其左還是右。例如對于一個“先增后減”的函數如果你在上升段取一個點函數值很大但極值點最大值既可能在它右邊繼續上升也可能在它左邊已經過了頂點開始下降。單個點提供的信息不足以做出決策。于是三分法的智慧就體現出來了通過兩個點來探測函數的“走勢”。將區間[l, r]分為三段取兩個中間點m1 l (r - l) / 3和m2 r - (r - l) / 3。比較f(m1)和f(m2)如果f(m1) f(m2)對于找最大值的單峰函數先增后減說明峰值點不可能在m1的左邊。因為如果峰值在左邊那么從峰值到m1是下降的而m1到m2是上升的這與“先增后減”的定義矛盾。因此我們可以安全地將左端點l更新為m1舍棄[l, m1)這段區間。如果f(m1) f(m2)同理峰值點不可能在m2的右邊可以將右端點r更新為m2舍棄(m2, r]。如果f(m1) f(m2)那么峰值點一定在[m1, m2]之間我們可以同時收縮左右端點令l m1,r m2。這樣每一次迭代我們都能夠確保極值點始終留在新的、更小的區間內并且區間長度以大約2/3的比例縮小。這是一種非常樸素而強大的“夾逼”思想。2.2 “凸函數”在算法中的具體含義在數學優化中凸函數的定義涉及二階導數非負或Jensen不等式。但在三分法的實用語境下我們所說的“凸函數”通常指的是單峰函數。更準確地當我們尋找最小值時我們要求函數是凸函數形狀像碗U型。當我們尋找最大值時我們要求函數是凹函數形狀像拱∩型。對于算法本身它只關心函數的單峰性質在定義域內存在唯一極值點且在該點左側函數單調右側函數單調方向相反。你的模板必須明確你是在找最大值還是最小值因為這決定了f(m1)和f(m2)比較后該舍棄哪一段區間。一個健壯的模板應該能通過一個參數或簡單的邏輯切換來適應這兩種情況。注意實際編程中很多“凸函數”并非嚴格的數學凸函數可能由多個分段函數組成但只要在搜索區間上滿足單峰性三分法就適用。這是其應用廣泛的重要原因。2.3 算法流程與復雜度分析標準三分法的流程可以清晰地分為以下幾步初始化確定搜索區間[l, r]和精度要求eps例如1e-7。迭代收縮當區間長度(r - l)大于eps時循環執行 a. 計算兩個三等分點m1 l (r - l) / 3,m2 r - (r - l) / 3。 b. 計算函數值f(m1)和f(m2)。 c.根據尋找最值的類型進行比較 - 找最小值若f(m1) f(m2)則r m2否則l m1。 - 找最大值若f(m1) f(m2)則l m1否則r m2。返回結果迭代結束后區間[l, r]內的任意點通常取(lr)/2都可作為極值點的近似。時間復雜度每次迭代區間長度乘以2/3。假設初始區間長度為L要求最終長度小于eps則迭代次數k滿足L * (2/3)^k eps解得k ≈ log_{3/2}(L/eps)。這是一個對數復雜度效率非常高。例如對于L1000,eps1e-7迭代次數大約在 60-70 次左右。空間復雜度為O(1)只需要常數級別的變量存儲。3. 核心實現細節與模板解析3.1 浮點數三分模板針對連續函數這是最經典的形式用于自變量為連續實數的函數。模板的核心在于循環條件和比較邏輯。// 尋找凸函數的最小值 double ternary_search_min(double l, double r) { const double eps 1e-10; // 精度根據題目要求調整 while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { r m2; // 最小值在 [l, m2] 區間 } else { l m1; // 最小值在 [m1, r] 區間 } } return (l r) / 2.0; // 返回近似極值點 } // 尋找凹函數的最大值 double ternary_search_max(double l, double r) { const double eps 1e-10; while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { l m1; // 最大值在 [m1, r] 區間 } else { r m2; // 最大值在 [l, m2] 區間 } } return (l r) / 2.0; }關鍵細節與解釋精度eps的選擇這是浮點數三分的靈魂。eps太小可能因浮點數精度問題陷入無限循環或產生誤差eps太大結果不精確。通常如果答案要求輸出小數點后k位eps可以設為1e-(k2)。例如要求輸出6位小數eps1e-8是個穩妥的選擇。有時也采用固定迭代次數如循環100次來替代精度判斷這樣更穩定。中間點計算務必使用l (r - l) / 3.0而非l (r - l) / 3后者在C/C中會導致整數除法。更安全的寫法是m1 l (r - l) / 3和m2 r - (r - l) / 3因為(r-l)是浮點數除以整數3會得到浮點結果。函數f的實現f(x)需要根據具體問題實現。它可能是一個簡單的數學表達式也可能是一個需要復雜模擬的過程如計算某種配置下的代價。確保f(x)在[l, r]上是單峰的這是算法正確的前提。3.2 整數三分模板針對離散函數當自變量是整數或者函數定義在整數域上時我們需要整數三分。因為區間長度是整數當區間縮小到很短時m1和m2可能重合需要不同的處理邏輯。// 在整數區間 [l, r] 上尋找凸函數的最小值 int ternary_search_int_min(int l, int r) { while (r - l 2) { // 當區間長度大于2時循環 int m1 l (r - l) / 3; int m2 r - (r - l) / 3; if (f(m1) f(m2)) { r m2; } else { l m1; } } // 區間長度小于等于3暴力枚舉剩余點 int min_val f(l); int ans l; for (int i l 1; i r; i) { int val f(i); if (val min_val) { min_val val; ans i; } } return ans; }整數三分的特殊之處循環條件常用while (r - l 2)。因為當區間長度小于等于3時兩個三分點m1和m2可能相等或無法有效分割區間此時直接暴力枚舉區間內所有整數點更簡單可靠。中間點計算使用整數除法。由于是整數(r-l)/3會向下取整。這保證了m1和m2是整數且l m1 m2 r。最終處理循環結束后區間[l, r]通常只剩下2到3個點。對這些點逐一計算函數值并比較得到最終的最優整數解。這是確保結果正確的關鍵步驟。3.3 通用模板與參數化設計一個更通用的模板可以整合尋找最大值和最小值甚至允許自定義比較函數提高代碼復用率。// 通用三分模板 // cmp: 一個函數接受兩個double/整數參數a,b當a優于b時返回true。 template typename T, typename Func T ternary_search(T l, T r, Func f, bool (*cmp)(T, T)) { const double eps 1e-10; // 對于浮點數 while (r - l eps) { // 整數版本需改為 while (r - l 2) T m1 l (r - l) / 3; T m2 r - (r - l) / 3; if (cmp(f(m1), f(m2))) { // 如果f(m1)比f(m2)更優根據三分邏輯更新端點 // 對于找最小值更優意味著更小cmp less // 對于找最大值更優意味著更大cmp greater // 更新邏輯需要根據cmp的具體含義來寫通常需要特化 // 更實用的寫法是下面兩個特化版本 } else { // 更新另一個端點 } } return (l r) / 2; } // 實踐中更清晰的寫法是提供兩個特化函數 double ternary_search_min(double l, double r, double (*f)(double)) { while (r - l 1e-10) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) r m2; else l m1; } return (l r) / 2; } double ternary_search_max(double l, double r, double (*f)(double)) { while (r - l 1e-10) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) l m1; else r m2; } return (l r) / 2; }4. 實戰應用場景與問題剖析三分法模板之所以重要是因為它能解決一系列看似棘手的問題。下面結合幾個典型場景看看如何將問題抽象成單峰函數求極值。4.1 場景一距離最值問題如“燈泡人”問題問題描述在一條數軸上有n個點其位置為a[i]?，F在要在這條數軸上找一個點x使得這個點到所有n個點的距離之和f(x) Σ|a[i] - x|最小。這是經典的絕對值和最小問題最優解是中位數。但如果代價不是距離而是距離的平方和f(x) Σ(a[i] - x)^2呢最優解是平均數。如果代價是更復雜的函數比如f(x) Σ sqrt((a[i] - x)^2 C)C為常數這就沒有簡單的解析解了。抽象與求解函數f(x) Σ sqrt((a[i] - x)^2 C)是一個凸函數可以證明其二階導非負。因此我們可以直接在數軸的可能范圍例如[min(a[i]), max(a[i])]內使用三分法尋找最小值點x。實現時只需編寫計算f(x)的函數然后套用浮點數三分求最小值的模板即可。實操心得這類問題的關鍵在于確定搜索區間[l, r]。通常極值點不會超出數據點的范圍所以將l設為min(a[i])r設為max(a[i])是安全的起點。有時根據問題物理意義區間可能需要適當擴大。4.2 場景二最優參數搜索如機器學習中的超參數調優問題描述假設你有一個機器學習模型其性能如準確率是某個連續超參數λ例如正則化系數的函數P(λ)。通過實驗你發現P(λ)隨著λ從0開始增大先上升后下降形成一個單峰曲線。你需要找到使準確率最高的λ。抽象與求解將P(λ)視為定義在λ的合理范圍如[0, 10]上的函數。由于它是單峰的我們可以用三分法來搜索最優的λ。這里的f(λ)就是模型在參數λ下的評估指標計算函數可能涉及訓練和驗證計算代價較高。注意事項計算成本每次計算f(λ)都可能需要重新訓練或驗證模型非常耗時。因此在設定三分精度eps時要權衡精度和計算成本。可能只需要中等精度就能找到足夠好的超參數。非嚴格單峰實際中的P(λ)可能不是嚴格的單峰可能存在多個局部極值。三分法只能找到局部最優且依賴于初始區間。在這種情況下三分法可能不如網格搜索或隨機搜索可靠。因此在將三分法應用于此類問題前務必通過初步實驗驗證函數在選定區間上的單峰性。4.3 場景三幾何最值問題如“穿越沙漠”問題描述一個經典問題是從點A到點B中間需要經過一條直線L。在A和B位于直線同側的情況下求從A到B經過直線L上一點P的最短路徑。這是一個光的反射原理問題解是使得入射角等于反射角的點。但如果速度在直線兩側不同呢問題就變成了在直線L上找一點P最小化|AP|/v1 |PB|/v2v1,v2為速度。抽象與求解設P點的坐標由其在直線上的某個參數t表示例如P A0 t * dir其中A0是直線上一點dir是方向向量。那么總時間T(t) |A - P(t)| / v1 |B - P(t)| / v2?？梢宰C明T(t)是關于t的凸函數。因此我們可以對參數t在其有效范圍內進行三分搜索尋找使T(t)最小的t。實現技巧計算f(t)時涉及距離計算。確保距離函數正確并且參數t的搜索區間[l, r]涵蓋了所有可能的P點通?？梢酝ㄟ^幾何關系確定。由于是連續函數使用浮點數三分模板。5. 常見陷阱、調試技巧與優化5.1 陷阱一函數非單峰這是三分法失敗的最主要原因。如果函數在搜索區間內有多個極值點多峰三分法很可能會收斂到某個局部極值點而非全局最優。排查與驗證繪制函數圖像如果可能在應用三分法前用程序在搜索區間內以較粗的粒度采樣并繪制f(x)的曲線圖直觀檢查單峰性。隨機測試在區間內隨機選擇大量的點對(x1, x2, x3)且x1 x2 x3檢查是否滿足凸性條件對于最小化問題f(x2) max(f(x1), f(x3))應大致成立。如果大量違反則函數非凸。領域知識從問題本身分析。很多物理、幾何問題天然具有凸性。經濟學的效用函數、距離的度量等也常常是凸的。5.2 陷阱二浮點數精度與循環終止浮點數運算存在精度損失。如果eps設置得過小如1e-15可能會因為浮點數誤差導致r - l始終無法小于eps從而陷入無限循環或提前終止在錯誤的位置。解決方案設置合理的eps根據問題對答案的精度要求來設定。通常比輸出要求高2個數量級足夠安全。使用迭代次數限制這是更穩健的做法。根據對數復雜度預先計算一個足夠的迭代次數。double ternary_search_min(double l, double r) { for (int i 0; i 100; i) { // 循環100次精度足夠高 double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) { r m2; } else { l m1; } } return (l r) / 2; }循環100次區間長度將縮小到原來的(2/3)^100 ≈ 2.5e-18倍對于絕大多數問題都綽綽有余。避免直接比較浮點數相等在比較f(m1)和f(m2)時如果擔心精度問題可以使用f(m1) eps f(m2)這樣的比較方式但通常直接比較在三分法中問題不大因為決定方向的是大小關系而非精確相等。5.3 陷阱三整數三分的邊界處理在整數三分中當區間長度很小時m1和m2可能相等。如果此時仍然按照f(m1)和f(m2)的比較來更新區間會導致區間無法繼續收縮。正確做法如前文模板所示當r - l 2時跳出主循環然后暴力枚舉區間[l, r]內的所有整數點。這是最安全、最清晰的做法。切勿嘗試在m1 m2時進行特殊邏輯處理那樣容易出錯。5.4 調試技巧打印日志在循環內打印l, r, m1, m2, f(m1), f(m2)的值。觀察區間是否在穩步縮小以及函數值的比較是否符合你對函數形狀的預期。驗證單峰性在最終區間內或隨機點上多計算幾個f(x)的值檢查是否滿足“先減后增”或“先增后減”的規律。與暴力枚舉對比對于小范圍問題可以寫一個暴力枚舉所有可能解以很小步長采樣的程序將三分法的結果與暴力枚舉的結果進行對比驗證正確性。檢查函數實現確保你編寫的f(x)函數是正確的。這是三分法的基礎往往錯誤就出在這里。特別是當f(x)涉及復雜計算或模擬時要單獨測試這個函數。5.5 性能優化三分法本身已經非常高效。優化點主要在于昂貴的f(x)計算記憶化如果f(x)是純函數且計算昂貴可以考慮緩存記憶化已經計算過的x對應的f(x)值。但在三分法中x是連續值很難直接命中緩存除非離散化。并行計算在一次迭代中f(m1)和f(m2)的計算是獨立的可以并行進行以提升速度?？s小初始區間盡可能利用問題性質縮小[l, r]的初始范圍減少迭代次數。例如通過求導、不等式分析或粗略估計確定極值點的大致位置。6. 模板的變體與擴展6.1 黃金分割法三分法將區間分成三等份。一個自然的想法是有沒有更優的分割比例黃金分割法0.618法就是一種選擇它每次迭代將區間長度縮小到原來的約0.618倍黃金分割比。與三等分相比黃金分割法的優勢在于它每次迭代只需要計算一個新的函數值因為其中一個點可以復用上一次迭代的點而三分法需要計算兩個新值。當f(x)計算非常昂貴時黃金分割法更有優勢。double golden_section_search(double l, double r) { const double phi (sqrt(5) - 1) / 2; // 約 0.618 double m1 r - phi * (r - l); double m2 l phi * (r - l); double f1 f(m1), f2 f(m2); while (r - l eps) { if (f1 f2) { // 找最小值 r m2; m2 m1; f2 f1; m1 r - phi * (r - l); f1 f(m1); } else { l m1; m1 m2; f1 f2; m2 l phi * (r - l); f2 f(m2); } } return (l r) / 2; }6.2 自適應三分與牛頓法對于導數容易求得的凸函數牛頓法或梯度下降法的收斂速度更快二階收斂。但三分法的優勢在于不需要導數信息適用性更廣。有一種混合策略先使用幾次三分法快速縮小區間然后在足夠小的區間內使用牛頓法進行精確求解。這結合了三分法的穩健性和牛頓法的快速收斂性。6.3 高維空間的最優值搜索標準的二分法和三分法只適用于一維搜索。對于多維變量的凸函數優化我們需要其他方法如梯度下降、共軛梯度法或更高級的優化算法。然而有時多維問題可以轉化為一系列一維問題例如坐標輪換法每次固定其他變量只優化一個變量這時就可以在該維度上使用一維搜索方法包括三分法。7. 從理解到精通思維訓練與題目推薦要真正掌握三分法不能只停留在套模板。我建議通過以下步驟進行思維訓練證明單峰性拿到一個問題首先嘗試從數學上證明或至少說服自己目標函數在搜索區間上是單峰的。思考它的導數符號變化或者利用幾何意義、不等式來論證。手動模擬對于一個小例子用紙筆手動模擬三分法的迭代過程感受區間是如何一步步縮小的。修改模板嘗試自己編寫支持尋找最大值、最小值的統一模板并增加對整數域和浮點數域的支持。解決變體問題嘗試解決一些三分法的變體問題例如尋找一個函數滿足f(x) target的x如果函數是單調的用二分如果是凸的可能需要結合三分和函數值比較。經典練習題推薦可在各大在線判題平臺搜索基礎/模板題直接考察三分法實現通常給出一個明顯的凸函數讓你求極值點。距離問題變種如前面提到的帶權距離和、復雜距離函數如加上平方根的最小化問題。幾何問題光線傳播、最佳觀測點、最短時間路徑等問題常能轉化為凸函數優化。物理問題涉及能量、時間最優的問題往往具有凸性。經濟模型一些簡單的成本、收益模型在特定假設下也是凸的。最后記住三分法是一個工具它的威力在于將“尋找最優”這個模糊的目標轉化為一個可以通過機械迭代精確逼近的過程。當你遇到一個求最值的問題并且感覺函數值隨著參數變化是“先好后壞”或“先壞后好”時不妨想想這會不會是一個單峰函數能不能用三分法來試試這種思維習慣的養成比記住十個模板更有價值。在實際編碼中我習慣將三分法函數封裝好并附上清晰的注釋說明是用于找最大值還是最小值輸入區間和精度要求是什么。這樣在競賽或項目遇到相關問題時我可以像調用庫函數一樣快速、準確地應用它把精力集中在問題建模和函數f(x)的實現上。