runtime 0 ms, beats 100% of cpp submissions
O(log(n)) solution with explanation

tags: binary search

Search in Rotated Sorted Array

📖 description

給定一個被旋轉過的 sorted array nums ，回傳 target 的 index

🧠 solution

在看到 sorted 的敘述時，其實就可以大概想到這個方法與 binary search 很有關聯了，但這題有點不一樣，因為陣列是被旋轉過的，因此在做 binary search 的時候會出現不同的狀態要討論

l 表示當前搜尋區間的下限
r 表示當前搜尋區間的上限
m 表示 (l+r)/2 ，也就是區間的中心點

ex.
    l        m        r
    4, 5, 6, 7, 0, 1, 2

此時有一個關鍵點，如果尋找中心點 nums[m] 的元素值比 nums[l] 大，表示搜尋區間的左半邊是排序好的，此時有兩種狀態。

  • 如果 target 的值比 nums[m] 小，且比 nums[l] 大，表示答案在左邊
  • 否則答案在右邊

而如果尋找中心點 nums[m] 的元素值沒有比 nums[l] 大，表示右邊是排序好的，此時也有兩種狀態。

  • 如果 target 的值比 nums[m] 大，且比 nums[r] 大，表示答案在右邊
  • 否則答案在左邊

⏳ time complexity

修改一點的 binary search ，時間複雜度 O(log(n))
總時間複雜度 O(log(n))

📝 code

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low=0,high=nums.size()-1;
        while(low<=high){
            int mid = (low+high)/2;     // 中點
            if(nums[mid]==target){      // 如果找到值回傳 index
                return mid;
            }
            if(nums[mid]>=nums[low]){   // 左半邊是排序好的
                if(target>=nums[low] && target<nums[mid]){
                    high = mid-1;       // 答案在左邊
                }
                else{
                    low = mid+1;        // 答案在右邊
                }
            }
            else{                       // 右半邊是排序好的
                if(target>nums[mid] && target<=nums[high]){
                    low = mid+1;        // 答案在右邊
                }
                else{
                    high = mid-1;       // 答案在左邊
                }
            }
        }
        return -1;
    }
};