33. Search in Rotated Sorted Array

題目 / Problem

中文： 給定一個原本按升序排列且元素互不相同的整數陣列 nums，它可能在某個未知的索引 k（1 <= k < nums.length）處被「左旋轉」過，變成 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。例如 [0,1,2,4,5,6,7] 左旋 3 格後變成 [4,5,6,7,0,1,2]。

給你旋轉後的陣列以及一個整數 target，回傳 target 在 nums 中的索引；若不存在則回傳 -1。演算法必須是 O(log n)。

English: You are given an integer array nums that was originally sorted in ascending order with distinct values, then possibly left-rotated at some unknown pivot k (1 <= k < nums.length). For example [0,1,2,4,5,6,7] rotated by 3 becomes [4,5,6,7,0,1,2]. Given the rotated array and target, return the index of target, or -1 if absent. The algorithm must run in O(log n) time.

Constraints / 限制： - 1 <= nums.length <= 5000 - -10^4 <= nums[i] <= 10^4 - All values are unique / 元素互不相同 - -10^4 <= target <= 10^4

Worked example / 範例： nums = [4,5,6,7,0,1,2], target = 0 → output 4 (因為 nums[4] == 0).

名詞解釋 / Glossary

• Binary search / 二分搜尋：在已排序的序列中，每次比較中間元素，然後丟掉一半搜尋範圍的演算法。時間複雜度 O(log n)。Repeatedly halves the search range by comparing against the middle element.
• Rotated sorted array / 旋轉排序陣列：一個原本排好序的陣列，在某個點被「切開」後把前半段接到後半段尾巴（或反之）。關鍵性質：把它從旋轉點切開後，左右兩半各自仍是升序。Cutting at the pivot leaves two halves that are each still ascending.
• Pivot / 旋轉點：旋轉後陣列中最小元素的位置；也是「降序斷層」發生的地方。The index where the original sort order "breaks".
• Invariant / 不變式：在迴圈每次迭代開始時都保持為真的條件。我們用它來證明二分搜尋是正確的。A condition guaranteed true at every loop iteration; used to reason about correctness.
• Mid-overflow trick / 中點防溢位寫法：用 left + (right - left) / 2 取中點而不是 (left + right) / 2，避免兩個大整數相加時溢位。Avoids integer overflow when summing two large indices.
• Half-open vs closed interval / 半開與閉區間：本文用「閉區間」[left, right]，意思是兩端都包含在搜尋範圍內，終止條件是 left > right。Closed interval [left, right] includes both endpoints; loop ends when left > right.

思路

最直觀的做法是線性掃描整個陣列找 target，這樣是 O(n)，但題目要求 O(log n)，所以必須用二分搜尋。問題在於陣列被旋轉過，不是單純的升序，因此不能直接套用標準二分。關鍵觀察是：當我們從中點 mid 把陣列切成兩半 [left, mid] 和 [mid, right] 時，至少有一半仍然是完全升序的——因為旋轉點只會落在其中一邊。於是我們每次先判斷哪一邊是有序的：如果 nums[left] <= nums[mid]，左半有序；否則右半有序。確認哪邊有序之後，就可以用 target 跟那邊的兩端比較，判斷 target 是否落在這個有序區間內：若落在裡面就往那邊搜，否則往另一邊搜。每次迭代仍把搜尋範圍砍掉一半，所以複雜度依然是 O(log n)。不變式是：若 target 存在於原陣列，它一定在當前的 [left, right] 區間內。

The naive approach is a linear scan, which is O(n) and violates the required O(log n). So we must use binary search, but the array is rotated, not strictly sorted — we need a twist. The key observation: when we pick a midpoint mid, the array splits into [left, mid] and [mid, right], and at least one of those halves is fully sorted, because the rotation pivot can only lie on one side. We detect which side is sorted by comparing nums[left] against nums[mid]: if nums[left] <= nums[mid], the left half is sorted; otherwise the right half is. Once we know which side is monotonic, we can check whether target lies within that sorted range by comparing it against the endpoints — if yes, recurse into that side; if no, recurse into the other. Each iteration halves the search space, preserving O(log n). The invariant maintained throughout: if target exists in the original array, it must still lie inside the current [left, right] window.

逐步走查 / Walkthrough

用 nums = [4,5,6,7,0,1,2], target = 0（索引 0 ~ 6）。

回傳 4，與預期相符。/ Returns 4 as expected.

Solution — C

/*
 * 演算法 / 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
}

Solution — C++

/*
 * 演算法 / 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
    }
};

複雜度 / Complexity

• Time: O(log n) — 每次迭代我們都把搜尋區間至少砍掉一半（不是走左半就是走右半），所以最多迭代 log₂ n 次，n 是 nums 的長度。Each iteration discards half of the current window, so we perform at most log₂ n iterations, where n = nums.length.
• Space: O(1) — 只用了幾個整數變數 left, right, mid；沒有遞迴、沒有額外陣列。Only a constant number of integer variables; no recursion stack, no auxiliary array.

Pitfalls & Edge Cases

• 判斷哪邊有序時用 <= 而非 < / Use <= not < when testing the sorted half：當 left == mid（區間長度為 2）時左半只有一個元素，必須視為「有序」，否則邏輯會走錯分支。When the window shrinks to size 2, left == mid; treating that as sorted (with <=) keeps the branching correct.
• 邊界比較要包含端點 / Endpoint inclusivity in the range check：判斷 target 是否在有序半邊時，一邊用閉、一邊用開（例如 nums[left] <= target && target < nums[mid]）來避免重複比較 nums[mid]（我們在迴圈開頭已比過了）。Mixing closed/open endpoints prevents redundant comparison with nums[mid], which was already tested at the top of the loop.
• 中點防溢位 / Overflow-safe midpoint：用 left + (right - left) / 2，不要寫 (left + right) / 2。雖然本題範圍小不會真的溢位，但這是好習慣。Always a good habit even when constraints are small.
• numsSize == 1 的單元素情境 / Single-element input：迴圈第一輪 left == right == mid，若 nums[0] != target 直接走到 return -1，邏輯依然正確。Handled naturally by the loop: one comparison then exit.
• target 不存在 / Target absent：迴圈會把 left 推過 right 自然終止，回傳 -1；不需要特別處理。Loop naturally terminates with left > right and returns -1.
• C++ 中 nums.size() 是無號型別 / size() is unsigned in C++：若 nums 為空，size() - 1 會 underflow 成超大值；本題保證 nums.length >= 1，但範例中仍先轉成 int 保險。Defensive cast to int avoids any unsigned underflow surprises.