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
4mo

Search for integers in a rotated sorted array efficiently.

  • Implement binary search to find the target integer in the rotated array.

  • Handle the rotation while performing binary search.

  • Return the index of...read more

Help your peers!
Select
Add answer anonymously...

Expedia Group Software Developer Intern interview questions & answers

A Software Developer Intern was asked Q. Minimum Distinct Labels Problem Statement You are given N boxes on a table, each...read more
A Software Developer Intern was asked Q. Encode the Message Problem Statement Given a text message, your task is to retur...read more
A Software Developer Intern was asked Q. Incremental Partitioning Problem Statement Given two integers N and K, determine...read more

Popular interview questions of Software Developer Intern

A Software Developer Intern was asked Q1. Minimum Distinct Labels Problem Statement You are given N boxes on a table, each...read more
A Software Developer Intern was asked Q2. Encode the Message Problem Statement Given a text message, your task is to retur...read more
A Software Developer Intern was asked Q3. Incremental Partitioning Problem Statement Given two integers N and K, determine...read more
Expedia Group Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

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

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits