DIY: Search in Rotated Sorted Array

Problem statement

Search for a given number in a sorted array of unique elements that have been rotated an arbitrary number. Assume that an array is rotated at some point unknown to you beforehand (For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]).

Return the index if the number is found. Otherwise, return -1.

Input

The input will be an array and an integer for which you have to find the index. The following is an example input:

arr = [4, 5, 6, 7, 0, 1, 2] 
key = 2

Output

The output will be an integer representing the index of key in arr. The following is an example output:

6

Coding exercise

Implement the searchRotated(arr, key) function, where arr is the rotated array and key is the number you have to find in arr. The function returns the index of key if it exists. Otherwise, it returns -1.