// 演算法：跟 C 版本一樣，用二分搜尋處理含重複元素的旋轉排序陣列。
// Algorithm: same as the C version — binary search on a rotated sorted array with duplicates.
// 用 std::vector<int> 取代裸指針，邏輯完全相同。
// We use std::vector<int> instead of a raw pointer; the logic is identical.

#include <vector>                        // 引入 vector 容器 / pull in the vector container

class Solution {
public:
    int findMin(std::vector<int>& nums) {
                                         // nums 以參考傳入，避免複製整個陣列 / passed by reference to avoid copying
        int lo = 0;                      // 左指針 / left pointer
        int hi = static_cast<int>(nums.size()) - 1;
                                         // 右指針；size() 回傳 size_t（無號），轉成 int 以避免警告
                                         // right pointer; size() returns size_t (unsigned), cast to int to avoid warnings

        while (lo < hi) {                // 至少有兩個元素時繼續 / continue while there are 2+ candidates
            int mid = lo + (hi - lo) / 2;
                                         // 中點，避免溢位寫法 / overflow-safe midpoint

            if (nums[mid] > nums[hi]) {  // 中點較大 → 最小值在右半 / mid is larger → min lies to the right
                lo = mid + 1;            // 整個左半（含 mid）都不可能是答案 / left half (incl. mid) cannot contain the answer
            } else if (nums[mid] < nums[hi]) {
                                         // 中點較小 → 最小值在左半或就是 mid / mid is smaller → min is in left half or is mid itself
                hi = mid;                // 保留 mid，因為它可能就是最小值 / keep mid as a candidate
            } else {                     // 相等：有重複元素的情況 / equal: the tricky duplicate case
                --hi;                    // 只丟掉 nums[hi]，因為 nums[mid] 等值能頂替 / drop only nums[hi]; nums[mid] equals it, so we don't lose the min
            }
        }

        return nums[lo];                 // lo == hi 時即為最小值索引 / when lo meets hi, it points to the minimum
    }
};