33. Search in Rotated Sorted Array

Medium
Description

給定一個旋轉過的升序整數陣列 nums（元素不重複）和一個目標值 target，搜尋 target 是否存在於陣列中。如果存在回傳其索引，否則回傳 -1。要求時間複雜度為 O(log n)。

Example:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Intuition#

旋轉陣列的左右半部至少有一邊是有序的，先判斷哪半邊有序，再決定 target 是否落在有序的那一半。

  • 取 mid 後，[left, mid] 或 [mid, right] 至少有一段是有序的
  • 如果 nums[left] <= nums[mid]，左半部有序：檢查 target 是否在 [left, mid) 內
  • 否則右半部有序：檢查 target 是否在 (mid, right] 內

Approaches#

1: Linear Scan#

  • 概念: 逐一掃描陣列找目標值
  • 時間複雜度: O(n)
  • 空間複雜度: O(1)
Linear Scan 程式碼
class Solution {
    fun search(nums: IntArray, target: Int): Int {
        for (i in nums.indices) {
            if (nums[i] == target) return i
        }
        return -1
    }
}
  • 概念: 每次判斷哪半邊有序，再判斷 target 是否在有序的那一半中
  • 時間複雜度: O(log n)
  • 空間複雜度: O(1)
class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (nums[mid] == target) return mid
            // 左半部有序
            if (nums[left] <= nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            } else {
                // 右半部有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
        }
        return -1
    }
}

判斷左半部有序時用 nums[left] <= nums[mid]（含等號），因為當 left == mid 時（只剩兩個元素），左半部只有一個元素，也算有序。

🔑 Takeaways#

  • Pattern: 旋轉排序陣列上的二分搜尋
  • 關鍵技巧: 先判斷哪半邊有序，再決定搜尋方向。這個「判斷有序半邊」的技巧是解決旋轉陣列問題的通用框架