Skip to content

LeetCode: 33-Search in Rotated Sorted Array 解題紀錄

題目

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

Prior to being passed to your function, nums is possibly rotated at an unknown pivot 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 rotated at pivot index 3 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.

Example 1:

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


Example 2:

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


Example 3:

Input: nums = [1], target = 0
Output: -1


Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104

解題思路

由於題目要求，我們只會 for 迴圈遍歷的話時間複雜度就會變成 O(n)，這就跟 O(log(n)) 的要求不符了。

看到 O(log(n)) 的要求後，自然閃過腦海的第一個想法就是二元搜索法（Binary Search）。

不過由於這是一個以某個軸點旋轉過後的遞增序列，所以我們的判斷式必須比原先單純的二元搜索更複雜些，需要考慮 5 種情況。

以下，我們使用 left 代表最左邊的數值、mid 代表中間值、right 代表為右邊的值。

  1. mid == target：完美命中，返回 mid 的 index
  2. mid >= left、left < target < mid：答案就在左側，把 right 值設定為 mid – 1
  3. mid >= left、target not in (left, mid)：答案不在左側，把 left 值設定為 mid + 1
  4. mid < left（代表 mid 已落在旋轉後的區段）、mid < target < right：答案就在右側，把 left 值設定為 mid + 1
  5. mid < left（代表 mid 已落在旋轉後的區段）、target not in (mid, right)：答案不在右側側，把 right 設定為 mid – 1

如果走完二元搜索（right < left）則代表答案不存在陣列中，返回 -1。


C++ 程式碼

class Solution {
public:
    int search(vector<int>& nums, int target) {        
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        
        while (left <= right) {
            mid = left + ((right - left) >> 1);

            if (nums[mid] == target) {
                return mid;
            }

            // If the left side is ordered
            if (nums[mid] >= nums[left]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            }
            // If the right side is ordered
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
};



Python 程式碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        mid = 0
        
        while left <= right:
            mid = left + ((right - left) >> 1);

            if nums[mid] == target:
                return mid

            # If the left side is ordered
            if nums[mid] >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            
            # If the right side is ordered
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

References

Read More

Tags:

Leave a Reply