Challenge: Search in a Rotated Array

Problem Statement

Given a sorted array of n integers that has been right rotated an unknown number of times, write code to find an element in the array. You may 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

int arr[] = {7, 8, 9, 0, 3, 5, 6}
int left = 0; // Index of the start of the array
int right = 6; // Index of the end of the array
int s = 3; // Element that is being searched for

Sample Output

4 // Index of the element that was searched for