Search Element in a Rotated Sorted Array

Given a sorted array that has been rotated, the task is to find the index of a specific element. The array is initially sorted in ascending order and then rotated clockwise by an unknown amount.

For example, a sorted array [1, 2, 3, 4, 5] rotated by 2 positions becomes [4, 5, 1, 2, 3].

You are required to answer multiple queries where for each query, you will search a particular element and return its index if found; otherwise, return -1.

Your goal is to achieve this in O(logN) time complexity for each query.

Input:

N A₁ A₂ A₃ ... A_N Q Q₁ Q₂ ... Q_Q

Output:

An integer representing the index of the searched element for each query, or -1 if the element is not found.

Example:

Input:

N = 5 A = 4 5 1 2 3 Q = 2 key = 1 key = 6

Output:

2 -1

Constraints:

1

Question

Search Element in a Rotated Sorted Array

Given a sorted array that has been rotated, the task is to find the index of a specific element. The array is initially sorted in ascending order and then rotated clockwise by an unknown amount.

For example, a sorted array [1, 2, 3, 4, 5] rotated by 2 positions becomes [4, 5, 1, 2, 3].

You are required to answer multiple queries where for each query, you will search a particular element and return its index if found; otherwise, return -1.

Your goal is to achieve this in O(logN) time complexity for each query.

Input:

N
A₁ A₂ A₃ ... A_N
Q
Q₁
Q₂
...
Q_Q

Output:

An integer representing the index of the searched element for each query, or -1 if the element is not found.

Example:

Input:

N = 5
A = 4 5 1 2 3
Q = 2
key = 1
key = 6

Output:

2
-1

Constraints:

1 <= N <= 10⁶
-10⁹ <= A[i] <= 10⁹
1 <= Q <= 500
-10⁹ <= Q[i] <= 10⁹
Time Limit: 1 sec

Note:

You only need to return the result, as printing is handled elsewhere.

Accepted Answer

Search for an element in a rotated sorted array efficiently in O(logN) time complexity.

Implement binary search to find the pivot point where rotation occurs.
Divide the array into two subarrays and perform binary search on the appropriate subarray.
Handle cases where the element may be in the left or right subarray after rotation.
Return the index of the element if found, else return -1.

Asked in Practo