題目網址: https://leetcode.cn/problems/search-in-rotated-sorted-array/

題意: 有一整數 array nums 按升序排列, 其中的值互不相同。

給一旋轉後的 array nums 和一整數 target, 如果 nums 中存在 target, 則返回其 index; 否則, 返回 -1。

請設計 $O(log(n))$ time 的演算法。

Solution：

想法：利用 Binary Search, 將 nums 從中間分開成左右兩部分的時候, 一定有一部分是有序的。

e.g. nums = [4,5,6,7,0,1,2], 從 6 切割, 可分成 [4,5,6] 和 [7,0,1,2] 兩個部分, 其中左邊 [4,5,6] 是有序的

因此我們可以在 Binary Search 時查看當前 mid 分割的兩個部分 [left, mid] 和 [mid + 1, right] 中哪個是有序的, 藉此來縮小左邊界 or 右邊界。

  • 若 target == nums[mid], 則直接返回 mid
  • 若 [left, mid] 是有序的, 且 target 界於 [nums[left], nums[mid]) 間, 則縮小搜索範圍為 [left, mid - 1]; 否則, 縮小搜索範圍為 [mid + 1, right]
  • 若 [mid + 1, right] 是有序的, 且 target 界於 (nums[mid], nums[right]] 間, 則縮小搜索範圍為 [mid + 1, right]; 否則, 縮小搜索範圍為 [left, mid - 1]

當 [left, mid] 區間恰好只有一個元素時, 也滿足左半邊已排序的定義

e.g. nums = [3, 1], target = 1

  • left = 0, right = 1, mid = 0 ➔ [left, mid] 區間恰好只有一個元素, 使得 nums[left] == nums[mid], 這時 target 應跟左半邊中的元素比較, 然後才縮小邊界
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;

            // 這種特殊的 Binary Search 建議搜到就返回
            if (nums[mid] == target) {
                return mid;
            }

            // 左半邊是被排序過的, e.g. [4,5,6,7,0,1,2], mid = 7
            // nums[left] == nums[mid] 也滿足左半邊是排序的定義（有可能 left == mid）
            if (nums[left] <= nums[mid]) {
                // 因為 target != nums[mid], 故用 < 即可
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // 右半邊是被排序過的, e.g. [7,0,1,2,4,5,6], mid = 2
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};
  • time：$O(log(n))$ ➔ Binary search
  • space：$O(1)$ ➔ 只需常數空間