There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 &lt;= k &lt; nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

&nbsp;
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 5000
	-104 &lt;= nums[i] &lt;= 104
	nums is guaranteed to be rotated at some pivot.
	-104 &lt;= target &lt;= 104


&nbsp;
Follow up: This problem is similar to&nbsp;Search in Rotated Sorted Array, but&nbsp;nums may contain duplicates. Would this affect the runtime complexity? How and why?

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        nums.sort()
        low=0
        high=len(nums)-1
        while low<=high:
            mid=(low+high)//2
            if nums[mid]==target:
                return True
            elif nums[mid]>target:
                high=mid-1
            else:
                low=mid+1
        return False
class Solution {
    public boolean search(int[] nums, int target) {
   if (nums == null || nums.length == 0) return false;
    
   int left = 0, right = nums.length-1;
    int start = 0;

//1. find index of the smallest element
    while(left < right) {
         while (left < right && nums[left] == nums[left + 1])
                ++left;
         while (left < right && nums[right] == nums[right - 1])
                --right;
        int mid = left + (right-left)/2;
        if (nums[mid] > nums[right]) {
            left = mid +1;
        } else right = mid;
    }
    
//2. figure out in which side our target lies
    start = left;
    left = 0;
    right = nums.length-1;
    if (target >= nums[start] && target <= nums[right])
        left = start;
    else right = start;
    
//3. Run normal binary search in sorted half.
    while(left <= right) {
        int mid = left + (right - left)/2;
        if (nums[mid] == target) return true;
        
        if (nums[mid] > target) right = mid-1;
        else left = mid + 1;
    }
    
    return false;
}
}
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        
        if( nums[0] == target or nums.back() == target ) return true; 
        // this line is redundant it reduces only the worst case when all elements are same to O(1)
        
        const int n = nums.size();
        int l = 0 , h = n-1;
        while( l+1 < n and nums[l] == nums[l+1]) l++;

        // if all elements are same
        if( l == n-1){
            if( nums[0] == target ) return true;
            else return false;
        }
        
        // while last element is equal to 1st element
        while( h >= 0 and nums[h] == nums[0] ) h--;
        int start = l , end = h;
        
        // find the point of pivot ie from where the rotation starts
        int pivot = -1;
        while( l <= h ){
            int mid = l + (h-l)/2;
            if( nums[mid] >= nums[0] ) l = mid+1;
            else {
                pivot = mid;
                h = mid-1;
            }
        }
        
        
        if( pivot == -1 ) l = start , h = end; // if no pivot exits then search space is from start -e end
        else {
            if( target > nums[end] ) l = start , h = pivot-1; // search space second half
            else l = pivot , h = end; // search space first half
        }
        
        // normal binary search
        while ( l <= h ){
            int mid = l + (h-l)/2;
            if( nums[mid] > target ) h = mid-1;
            else if( nums[mid] < target ) l = mid+1;
            else return true;
        }
        
        return false;
        
    }
};
var search = function(nums, target) {
    let found = nums.findIndex(c=> c==target);
    if(found === -1) return false
    else
        return true
};
Search in Rotated Sorted Array II