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