Problem: Search In Rotated Sorted Array

Given a sorted array that has been rotated clockwise by an unknown amount, you need to answer Q queries. Each query is represented by an integer Q[i], and you must determine if this integer exists in the rotated array. Return the index if found, otherwise return -1.

Input:

The first line contains an integer N, representing the size of the array.
The second line contains N space-separated integers, representing the elements of the array A.
The third line contains an integer Q, representing the number of queries.
The next Q lines each contain a single integer Q[i], the number to search for in the array.

Output:

For each query, output the index of the number if found; otherwise, output -1. Each output should be on a new line.

Example:

Input:
N = 5
A = [4, 5, 6, 7, 0, 1, 2]
Q = 3
Q[i] = [0, 3, 6]

Output:
4
-1
2

Constraints:

  • 1 ≤ N ≤ 10^6
  • -10^9 ≤ A[i] ≤ 10^9
  • 1 ≤ Q ≤ 500
  • -10^9 ≤ Q[i] ≤ 10^9
  • Time Limit: 1 sec

Note:

The problem requires solving each query in O(logN) time complexity.
AnswerBot
1y

This is a problem where a sorted array is rotated and we need to search for given numbers in the array.

  • The array is rotated clockwise by an unknown amount.

  • We need to search for Q numbers in the rotate...read more

Help your peers!
Add answer anonymously...
Sigmoid Data Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter