0033-Search-in-Rotated-Sorted-Array

Problem Description

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Constraints:

• All values of nums are unique.

Solution

核心觀念：旋轉後的陣列是兩段各自遞增、且左段每個元素都大於右段每個元素（跟 0153-Find-Minimum-in-Rotated-Sorted-Array 同一個結構）。二分法本身要求全域單調，這裡不成立，所以每一輪得多做一件事：先判斷中點落在哪一段，再用那一段的值域夾擠 target。

   4  5  6  7 │ 0  1  2        p ＝ 4（最小值下標 ＝ 旋轉點）
   └─左段(大)─┘ └右段(小)┘

   左段 nums[l..p-1]：遞增，值全部 > nums[r]
   右段 nums[p..r]  ：遞增，值全部 ≤ nums[r]   ← nums[r] 是右段的最大值

   所以只要比 nums[m] 和 nums[r]，就知道 m 落在哪一段：
     nums[m] ≤ nums[r] → m 在右段
     nums[m] >  nums[r] → m 在左段

方法一：比右端點 — O(log n)／O(1)（推薦）

完整的情況分析。p 是最小值下標，僅用於推導：

0. nums[m] == target                          → return m
1. nums[m] ≤ nums[r]（m 在右段，含 m == r）
     nums[m] < target ≤ nums[r] → target ∈ [m+1, r]                → l = m+1
     否則                         → target ∈ [p, m-1] 或 [l, p-1]   → r = m-1
2. nums[m] > nums[r]（m 在左段）
     nums[r] < target < nums[m]  → target ∈ [l, m-1]               → r = m-1
     否則                         → target ∈ [m+1, p-1] 或 [p, r]   → l = m+1

// Time: O(log n)
// Space: O(1)
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
      int m = l + (r - l) / 2;
      if (nums[m] == target) return m;
      if (nums[m] <= nums[r]) {                                 // m 在右段（含 m == r）
        if (nums[m] < target && target <= nums[r]) l = m + 1;
        else r = m - 1;
      } else {                                                  // m 在左段
        if (nums[r] < target && target < nums[m]) r = m - 1;
        else l = m + 1;
      }
    }
    return -1;
  }
};

有 nums[m] == target 這張授權書，所以兩邊都能安全地 ±1，屬於 Binary-Search-Templates 的模板一。出口是區間變空 l > r。

情況 1： if  成立 → l = m+1   ← 向右在 if，等號必須寫進條件
情況 2： else 成立 → l = m+1   ← 向右在 else，等號白撿

方法二：判斷左半是否有序 — O(log n)／O(1)

教科書最常見的形式。改問「[l, m] 這一段有沒有被斷點切開」，不去定位段別：

// Time: O(log n)
// Space: O(1)
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
      int m = l + (r - l) / 2;
      if (nums[m] == target) return m;
      if (nums[l] <= nums[m]) {                                 // [l, m] 有序
        if (nums[l] <= target && target < nums[m]) r = m - 1;
        else l = m + 1;
      } else {                                                  // [m, r] 有序
        if (nums[m] < target && target <= nums[r]) l = m + 1;
        else r = m - 1;
      }
    }
    return -1;
  }
};

方法三：先找斷點，再對虛擬展開的序列二分 — O(log n)／O(1)

另一條路：先用 0153-Find-Minimum-in-Rotated-Sorted-Array 求出斷點 p，之後把 nums 當成虛擬的完整遞增陣列 A[i] = nums[(i + p) % n] 來搜。第二段就退化成零判斷的標準二分。

// Time: O(log n)
// Space: O(1)
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int n = nums.size();
    int l = 0, r = n - 1;
    while (l < r) {                        // 模板二：找最小值下標
      int m = l + (r - l) / 2;
      if (nums[m] > nums[r]) l = m + 1;
      else r = m;
    }
    int p = l;
    l = 0, r = n - 1;
    while (l <= r) {                       // 模板一：在虛擬展開的遞增序列上找 target
      int m = l + (r - l) / 2;
      int i = (m + p) % n;
      if (nums[i] == target) return i;
      if (nums[i] < target) l = m + 1;
      else r = m - 1;
    }
    return -1;
  }
};

兩次二分是 2 · O(log n)，仍是 O(log n)。不要真的重排陣列（那會變 O(n)），% n 只是座標映射。

三種寫法實測（窮舉長度 1~12 的所有旋轉 × 所有 target，共 1456 組）全數通過。方法一是首選：只有一套下標、可以完整推導、且能延伸到 81。

Related Problems

Binary-Search-Templates — 本題屬「模板一 · 找 target」，因為有 nums[m] == target 這個明確出口；模板選擇與區間慣例的完整規則都在這篇
0153-Find-Minimum-in-Rotated-Sorted-Array — 同一種旋轉陣列結構，但因為是找邊界而改用模板二，最好的對照組；方法三直接把它當子程序用
0081-Search-in-Rotated-Sorted-Array-II — 允許重複值的版本，斷點無法二分定位，只有方法一、二的形狀能延伸，最壞退化成 O(n)
0704-Binary-Search — 模板一最乾淨的原型，方法三的第二段就是它
0034-Find-First-and-Last-Position-of-Element-in-Sorted-Array — 同樣是「找 target」但要求邊界，展示明確出口消失後為何得換模板二