targetElementInRotatedSortedArray2

class Solution {
public:
bool search(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] == target)
            return true;
        else if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
            low = low + 1;
            high = high - 1;
        } else if (nums[mid] >= nums[low]) { // array is sorted till mid
            if (nums[mid] >= target && nums[low] <= target) // target in between low and mid
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            if (nums[mid] <= target && nums[high] >= target)  // target between mid and high
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    return false;
}

};

• The following test checks whether low, mid and mid,high are equal.
• When this case is met, we already know that
  1. mid != target
  2. since low = mid = target, the array was rotated at the current element; thus the result lie between low and high, so we shrink each boundary by 1.

     else if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                 low = low + 1;
                 high = high - 1;
             }