Search Element in Rotated Sorted Array II

The problem statement is as follows: given a goal value k and an integer array arr of size N, sorted in ascending order (may contain identical values). The array is now rotated at an unidentified pivot point. If k is present, return True; if not, return False.

Solution: In a sorted array, how does rotation take place?
Consider the following sorted array: {1, 2, 3, 4, 5}. This array will become {4, 5, 1, 2, 3} if we rotate it at index 3. Essentially, we shifted the remaining components to the right and the element at the last index to the front. This procedure was carried out twice.

Brute Force Approach

The linear search method is one simple strategy we can take into account. In order to determine whether the target is present in the array, we will use this technique to traverse it. We shall just return True if it is found; if not, we will return False.

Algorithm:

• We will go through the array, verifying that each element equals k. We shall return True if we discover any elements.
• If not, False will be returned.

C++

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

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;
    }
    return false;
}

int main()
{
    vector<int> arr = {7, 8, 1, 2, 3, 3, 3, 4, 5, 6};
    int k = 3;
    bool ans = searchInARotatedSortedArrayII(arr, k);
    if (!ans)
        cout << "Target is not present.\n";
    else
        cout << "Target is present in the array.\n";
    return 0;
}

Java

import java.util.*;

public class tUf {
    public static boolean searchInARotatedSortedArrayII(int []arr, int k) {
        int n = arr.length; // size of the array.
        for (int i = 0; i < n; i++) {
            if (arr[i] == k) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {7, 8, 1, 2, 3, 3, 3, 4, 5, 6};
        int k = 3;
        boolean ans = searchInARotatedSortedArrayII(arr, k);
        if (ans == false)
            System.out.println("Target is not present.");
        else
            System.out.println("Target is present in the array.");
    }
}

Python

from typing import *
def searchInARotatedSortedArrayII(arr : List[int], k : int) -> bool:
    for num in arr:
        if num == k:
            return True
    return False

if __name__ == "__main__":
    arr = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6]
    k = 3
    ans = searchInARotatedSortedArrayII(arr, k)
    if not ans:
        print("Target is not present.")
    else:
        print("Target is present in the array.")

JavaScript

function searchInARotatedSortedArrayII(arr, k) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === k) {
            return true;
        }
    }
    return false;
}

let arr = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6];
let k = 3;
let ans = searchInARotatedSortedArrayII(arr, k);
if (!ans) {
    console.log("Target is not present.");
} else {
    console.log("Target is present in the array.");
}

Output: Target is present in the array.Complexity Analysis

Time Complexity: O(N), N = size of the given array.

Space Complexity: O(1)