極值問題

在演算法問題中，常常會遇到需要找到一個最優解的情況，例如最大值、最小值等，此時我們可以考慮使用二分搜來加速求解。二分搜不僅可以應用於有序數組中尋找目標值，也可以推廣到求解極值問題。

什麼是極值問題?

#

極值問題指的是在一個定義域內尋找最大值或最小值的問題。通常我們可以將問題簡化為一個目標函式 f(x)，需要在 x 的定義域內找到 f(x) 的最大值或最小值。

二分搜解決極值問題

#

對於一個單調函式f(x)，我們可以使用二分搜來尋找極值。具體步驟如下：

1. 確定目標函式 f(x) 的定義域，設為 [l, r]。
2. 在定義域內二分取中點 mid = (l + r) / 2。
3. 計算 f(mid) 的值，並根據單調性判斷極值是在 [l, mid] 還是 [mid + 1, r] 中。
4. 更新搜索區間，繼續二分搜。
5. 重複步驟 2-4 直至搜索區間足夠小，得到近似極值。通常如果搜索區間恆為整數，二分搜終止條件是r - l = 1。

假設現在有一個左邊遞增，右邊遞減的陣列或vector，你可以假設v[x]就是剛剛說的f(x)，對他二分搜就可以得到極值，範例程式碼如下：

#include <bits/stdc++.h>
using namespace std;

int findPeakElement(vector<int>& nums) {
    int l = 0, r = nums.size(); // l 跟 r 永遠不會被搜到，除非只有一個元素
    while (r - l != 1) { // 如果遇到r - l = 1沒有停下來，就會無窮迴圈(想一想，為什麼)
        int mid = (l + r) / 2;
        if (nums[mid] < nums[mid + 1]) { // 左半是單調遞增，右邊是單調遞減
            // 極值在右半段
            l = mid + 1;
        } else {
            // 極值在左半段或mid處
            r = mid;
        }
    }
    // 最終l和r重合在極值點
    return r;
}

int main() {
    vector<int> nums = {1, 3, 5, 7, 9, 8, 6, 4, 2};
    int peak = findPeakElement(nums);
    cout << "Peak element is: " << nums[peak] << endl;
    return 0;
}

輸出：

Peak element is: 9

在上述程式碼中：

1. 我們定義了一個函式 findPeakElement。
2. 在函式內部，我們使用變量 l 和 r 分別表示數組的左右邊界。
3. 我們使用一個 while 迴圈進行二分搜，每次比較中點元素 nums[mid] 與其左右鄰居的大小關係。根據比較結果，我們更新邊界 l 或 r，繼續二分搜。
4. 迴圈退出時，l 和 r 重合在極值點上。我們返回 r 作為極值點的索引。
5. 在 main 函式中，我們定義了一個單峰數組 nums，並調用 findPeakElement 函式找到極值點的索引。最後我們輸出該極值點的值。

當然，你可以真的搜一個單峰函式，好比說你熟知的二次函式之類的。不過有時候二分搜會動用浮點數，所以要注意之前提到過的精度問題。