Problem Statement

Given an integer array nums, sorted in ascending order (may contain duplicate values) and a target value k. Now the array is rotated at some pivot point unknown to you. Return True if k is present and otherwise, return False.

Examples

Example 1:

Input: nums = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6], k = 3
Output: True

Explanation: The element 3 is present in the array. So, it would return True.

Example 2:

Input: nums = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6], k = 10
Output: False

Explanation: The element 10 is not present. So, it would return False.

Different Approaches

1️⃣ Linear Search

Intuition:

The simplest way to solve this problem is by using a linear search to check each element of the array one by one.

Approach:

1. Traverse the array from start to end & compare each element with the target value.
2. If an element matches the target, return True. If no match is found by the end of the array, return False.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to search for the target element in a rotated sorted array
    bool searchInARotatedSortedArrayII(vector<int>& arr, int target) {
        int n = arr.size(); 
        
        // Traverse the array to find the target element
        for (int i = 0; i < n; i++) {
            // If the current element matches the target, return true
            if (arr[i] == target) return true;
        }
        // If the target is not found, return false
        return false;
    }
};

int main() {
    vector<int> arr = {7, 8, 1, 2, 3, 3, 3, 4, 5, 6}; 
    int target = 3; 

    // Create an instance of the Solution class
    Solution sol;

    // Function call to search for the target element
    bool result = sol.searchInARotatedSortedArrayII(arr, target);

    if (!result)
        cout << "Target is not present.\n";
    else
        cout << "Target is present in the array.\n";

    return 0;
}

2️⃣ Binary Search

Intuition:

For looking for a target in a rotated sorted array that has duplicates, use binary search for most optimal results. The tricky part is handling duplicates, especially when they are at both ends of the array. Start by finding the sorted half of the array and checking if the target is there. If duplicates make it hard to find the sorted half, just skip them by moving our pointers. This way, keep narrowing down the search space efficiently.

Approach:

1. Initialize two pointers: low at the start and high at the end of the array.
2. Inside a loop, calculate the midpoint (mid). 
   1. If arr[mid] is the target, return True.
   2. Check if arr[low], arr[mid], and arr[high] are equal. 
      1. If so, increment low and decrement high to skip duplicates.
   3. Identify the sorted half: If arr[low] <= arr[mid], the left half is sorted. Otherwise, the right half is sorted.
   4. Adjust the pointers based on the target's location:
      1. If the left half is sorted and the target is within this range, adjust high to mid - 1. Otherwise, adjust low to mid + 1.
      2. If the right half is sorted and the target is within this range, adjust low to mid + 1. Otherwise, adjust high to mid - 1.
   5. Continue this process until low exceeds high. If no target is found, return False.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /*  Function to search for the target element 
        in a rotated sorted array with duplicates   */
    bool searchInARotatedSortedArrayII(vector<int>& arr, int target) {
        int n = arr.size();
        int low = 0, high = n - 1;
        
        // Applying binary search algorithm 
        while (low <= high) {
            int mid = (low + high) / 2;

            // Check if mid points to the target
            if (arr[mid] == target) return true;

            // Handle duplicates: if arr[low], arr[mid], and arr[high] are equal
            if (arr[low] == arr[mid] && arr[mid] == arr[high]) {
                low = low + 1;
                high = high - 1;
                continue;
            }

            // Check if the left part is sorted
            if (arr[low] <= arr[mid]) {
                /*  Eliminate the right part if target
                    exists in the left sorted part */
                if (arr[low] <= target && target <= arr[mid]) {
                    high = mid - 1;
                } 
                // Otherwise eliminate the left part
                else {
                    low = mid + 1;
                }
            } else {
                /*  If the right part is sorted and
                    target exists in the right sorted
                    part, eliminate the left part   */
                if (arr[mid] <= target && target <= arr[high]) {
                    low = mid + 1;
                } 
                // Otherwise eliminate the right part
                else {
                    high = mid - 1;
                }
            }
        }
        // If target is not found
        return false;
    }
};

int main() {
    vector<int> arr = {7, 8, 1, 2, 3, 3, 3, 4, 5, 6};
    int target = 3; 

    // Create an instance of the Solution class
    Solution sol;

    // Function call to search for the target element
    bool result = sol.searchInARotatedSortedArrayII(arr, target);

    if (!result)
        cout << "Target is not present.\n";
    else
        cout << "Target is present in the array.\n";

    return 0;
}

Complexity Analysis:

• Time Complexity: O(logN) for the best and average cases. As in the best and average scenarios, the binary search algorithm is primarily used and hence the time complexity is O(logN).
  However, in the worst-case scenario, it'll be O(N/2) where all array elements are the same but not the target (e.g., given array = {3, 3, 3, 3, 3, 3, 3}), we continue to reduce the search space by adjusting the low and high pointers until they intersect, which will end up taking O(N/2) time complexity.
• Space Complexity: O(1), as we are not using any extra space to solve this problem.