/*
 * 演算法 / Algorithm:
 *   與 C 版相同：在閉區間做改良版二分，每次判斷哪一半有序再決定走向。
 *   Same as the C version: modified binary search on a closed interval; each
 *   iteration identifies the sorted half and narrows toward target.
 */

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // vector<int> 是 C++ 標準動態陣列；用 .size() 取長度（型別為 size_t，無號）
        // vector<int> is the STL dynamic array; .size() returns an unsigned size_t
        int left = 0;                                  // 左端索引 / left bound (inclusive)
        int right = static_cast<int>(nums.size()) - 1; // 轉成 int 避免無號減 1 變超大值
                                                       // cast to int so size()-1 doesn't underflow when size()==0

        while (left <= right) {                        // 閉區間非空 / non-empty closed interval
            int mid = left + (right - left) / 2;       // 防溢位中點 / overflow-safe midpoint
            if (nums[mid] == target) {                 // 找到目標 / found target
                return mid;
            }

            if (nums[left] <= nums[mid]) {             // 左半升序 / left half is sorted
                // target 在左半的有序區間內？ / is target inside the sorted left range?
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;                   // 收縮右端 / shrink from the right
                } else {
                    left = mid + 1;                    // 收縮左端 / shrink from the left
                }
            } else {                                   // 右半升序 / right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;                    // target 在右半 / target lies right
                } else {
                    right = mid - 1;                   // 否則往左 / otherwise go left
                }
            }
        }

        return -1;                                     // 沒找到 / not found
    }
};