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 search_rotated(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.