【LeetCode】 33. Search in Rotated Sorted Array

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).

假設有一個排序過的漸增陣列在某個未知的軸心被旋轉。
(舉例：[0,1,2,4,5,6,7] 可能變成 [4,5,6,7,0,1,2])。
給你一個目標值去搜尋，如果存在於陣列中請回傳索引值，否則回傳-1。
你可以假設陣列中不會存在重複的值。
你的演算法的時間複雜度必須在O(log n)之內。

Example:

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

Solution

• 排序過的陣列、O(log n)的時間，可以很直覺地想到二分搜尋法。
• 以上面Example為例，原本的漸增陣列因旋轉出現 7 到 0 的減少，這邊將這個減少稱作【斷層】。
• 我們只需要將陣列拆成兩個區塊，分別都沒有斷層就可以使用二分搜尋法了。
• 如何確定陣列中沒有斷層？檢查第一個元素有沒有小於最後一個元素即可。
  • 如果小於：二分搜尋。
  • 如果大於，往中間切一半，分別丟入遞迴。

Code

class Solution {
public:
    int Binary_Search(vector<int>& nums, int target, int s, int e)
    {
        if(e < s) return -1;
        int mid = (s + e) / 2;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            return Binary_Search(nums, target, s, mid - 1);
        else
            return Binary_Search(nums, target, mid + 1, e);
    }
    
    int Find(vector<int>& nums, int target, int s, int e)
    {
        if(e < s) return -1;
        if(e == s)
        {
            if(nums[e] == target)
                return e;
            return -1;
        }
        if (nums[s] < nums[e])
        {
            return Binary_Search(nums, target, s, e);
        }
        else
        {
            int mid = (s + e) / 2;
            if(nums[mid] == target)
                return mid;
            else
            {
                return max(Find(nums, target, s, mid),
                          Find(nums, target, mid + 1, e));
            }
        }
    }
    
    int search(vector<int>& nums, int target) {
        return Find(nums, target, 0, nums.size() - 1);
    }
};

tags: LeetCode C++