Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Search In Rotated Sorted Array
MEDIUM
30 mins
229 upvotes
Binary Search
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Binary Search
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Search In Rotated Sorted Array

Contributed by
Ashwani
Medium
yellow-spark
0/80
Avg time to solve 30 mins
Success Rate 65 %
Share
229 upvotes

Problem Statement

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?
Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1:
4
2 5 -3 0
2
5
1
Sample Output 1:
1
-1
Explanation For Sample Input 1:
In the 1st test case, 5 is found at index 1

In the 2nd test case, 1 is not found in the array, hence return -1.
Sample Input 2:
5
100 -2 6 10 11
2
100
6
Sample Output 2:
0
2
Reset Code
Full screen
Auto
copy-code
Console