Challenge: Search in a Rotated Array

Problem statement

Given a sorted array of n integers that has been rotated an unknown number of times, write some code to find an element in the array. Assume that the array was originally sorted in ascending order.

Input

A sorted array that has been rotated a number of times.

Output

The index of the element.

Sample input

arr = {7, 8, 9, 0, 3, 5, 6};
n = size of the array
key = 3; // Element that is being searched for

Sample output

result = 4; // Index of the element that was searched for