Data Scientist

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) ?

There is a list of N files, and each file has a given file ID. Array ‘ARR’ contains the list of all file IDs.Ninja’s task is to tell whether a file with ID = ‘VAL’ exists in the list or not. So, to answer the query quickly, Ninja sorted the list. But, due to system error, the sorted array got rotated at an unknown pivot. Can you help Ninja with this problem?

You are given a rotated sorted array ‘ARR’ having ‘N’ elements and an integer ‘VAL’. You to check whether ‘VAL’ exists in the given array or not.

For Example

If the ARR is [4,6,9,11,1,2,2] and ‘VAL’ is 4, the answer will be ‘YES’ as 4 exist in ‘ARR’.