題目： LeetCode - 33. Search in Rotated Sorted Array

題目說明

給一個排序過的陣列，但是反轉一部份，給一個 target 求它在陣列中的 index，若不在陣列中則回傳 - 1。
※ 題目希望時間複雜度為 O(log n)

解題思路

基本為二分搜尋法，但是因為陣列反轉過，所以會有一些其他的規則，舉例子並自己設 target 就能找出其中的規則。
以下是我觀察到的規則：

  • 如果 nums[mid] > target
    • 如果 nums[0] > nums[mid] 則 target 會在左邊這一段。
    • 如果 nums[0] < nums[mid]
      • 如果 nums[0] > target 則 target 會在右邊這一段。
      • 如果 nums[0] < target 則 target 會在左邊這一段。
  • 如果 nums[mid] < target
    • 如果 nums[0] > nums[mid]
      • 如果 nums[0] > target 則 target 會在右邊這一段。
      • 如果 nums[0] < target 則 target 會在左邊這一段。
    • 如果 nums[0] < nums[mid] 則 target 會在右邊這一段。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(true)
        {
            if(left == right)
                return -1;
            
            int mid = (left + right) / 2;
            if(nums[mid] == target)
                return mid;
            
            if(nums[mid] > target)
                if(nums[0] > nums[mid])
                    right = mid;
                else
                    if(nums[0] > target)
                    
                        left = mid + 1;
                    else
                        right = mid;   
            
            if(nums[mid] < target)
                if(nums[0] > nums[mid])
                    if(nums[0] > target)
                        left = mid + 1;
                    else
                        right = mid;
                else
                    left = mid + 1;
        }
        return -1;
    }
};