LeetCode 81 Search in Rotated Sorted Array II [binary search]

LeetCode 81 Search in Rotated Sorted Array II [binary search] <c++>

给出排序好的一维有重复元素的数组，随机取一个位置断开，把前半部分接到后半部分后面，得到一个新数组，在新数组中查找给定数是否存在，时间复杂度限制\(O(log_2n)\)

C++

因为有重复元素存在，nums[l] <= nums[mid]不能说明[l,mid]区间内一定是单调的，比如数组[1,2,3,1,1,1,1]，但是严格小于和严格大于的情况还是可以判断的。所以当nums[l] == nums[mid]时，令l++，跳过这个重复元素。所以其实该算法最坏情况下(所有元素相同)时间复杂度是\(O(n)\)的。

class Solution {
public:
    bool search(std::vector<int>& nums, int target) {
        int l = 0,r = nums.size();
        while (l<r){
            const int mid = l + (r-l)/2;
            if(nums[mid] == target) return true;
            if(nums[l] < nums[mid]) // [l,mid]区间单调不降
                if(nums[l] <= target && target < nums[mid]) r = mid; // target 在区间内
                else l = mid + 1; // target 不在区间内
            else if(nums[mid] < nums[l]) // [mid,r]区间单调不降
                if(nums[mid] < target && target <= nums[r-1]) l = mid + 1; // target 在区间内
                else r = mid; // target 不在区间内
            else l++; //跳过这个重复元素
        }
        return false;
    }
};

Java

Python3