/*
 * 演算法 / Algorithm:
 *   在閉區間 [left, right] 做改良版二分搜尋；每次先判斷 mid 把陣列分成的兩半
 *   哪一半是完全升序的，再決定 target 落在哪一半。
 *   Modified binary search on closed interval [left, right]: each step decides
 *   which half (split by mid) is fully sorted, then narrows toward target.
 */

int search(int* nums, int numsSize, int target) {
    int left = 0;                          // 搜尋區間左端（含） / left bound of search window, inclusive
    int right = numsSize - 1;              // 搜尋區間右端（含） / right bound, inclusive

    while (left <= right) {                // 區間非空時繼續 / continue while window is non-empty
        int mid = left + (right - left) / 2;  // 防溢位的中點寫法 / overflow-safe midpoint
        // 直接命中就回傳索引 / direct hit: return the index immediately
        if (nums[mid] == target) {
            return mid;
        }

        // 判斷左半 [left..mid] 是否升序 / check if the left half is sorted
        // 因為元素互不相同，這裡用 <= 仍安全（left==mid 時左半只有 1 個元素，視為有序）
        // distinct values, so <= is safe even when left == mid (a 1-element range is trivially sorted)
        if (nums[left] <= nums[mid]) {
            // 左半有序：檢查 target 是否落在 [nums[left], nums[mid]) 內
            // left half is sorted: see if target lies inside [nums[left], nums[mid])
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;           // target 在左半，砍掉右半 / discard right half
            } else {
                left = mid + 1;            // target 不在左半，往右半找 / search right half
            }
        } else {
            // 否則右半 [mid..right] 必為升序 / otherwise the right half must be sorted
            // 檢查 target 是否落在 (nums[mid], nums[right]] 內 / check (nums[mid], nums[right]]
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;            // target 在右半，砍掉左半 / discard left half
            } else {
                right = mid - 1;           // 否則往左半找 / search left half
            }
        }
    }

    return -1;                             // 區間空了仍沒找到 / window exhausted, target absent
}