81. Search in Rotated Sorted Array II

發表於 | 分類於

problem

solution

如果最左邊或最右邊與中間一樣(因為可能重複數值)，就往將右索引往左移動一個

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n-1;
        while(l<=r){
            int mid = l+ (r-l)/2;
            if(nums[mid] == target) return true;
            // 右半部遞增
            else if(nums[mid] < nums[r]){
                if(nums[mid] < target && target<= nums[r]) l = mid+1;
                else r = mid-1;
            }
            else if(nums[mid] > nums[r]){
                if(nums[l] <= target && target < nums[mid]) r = mid-1;
                else l = mid+1;
            }
            else r--;
        }
        return false;
    }
};

analysis

  • time complexity O(logn)
  • space complexity O(1)