Brute Force

Algorithm

We will traverse the array and check every element if it is equal to k. If we find any element, we will return True.
Otherwise, we will return False.

Code

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

// Class to encapsulate search logic
class Solution {
public:
    // Linear search in rotated sorted array (with duplicates)
    bool searchInARotatedSortedArrayII(vector<int>& arr, int k) {
        int n = arr.size(); // size of the array
        for (int i = 0; i < n; i++) {
            if (arr[i] == k) return true; // if found, return true
        }
        return false; // not found
    }
};

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

    // Create object of Solution class
    Solution obj;
    bool ans = obj.searchInARotatedSortedArrayII(arr, k);

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

    return 0;
}