Challenge: Search in a Rotated Array

Let's write a function to search in a sorted and rotated array.

Problem statement

Given a sorted array of n integers that has been 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}    // Given Array
int left = 0;     // Starting Index of the Array
int right = 6;    // Ending Index of the Array
int n = 3;        // Key to Search

Sample output

4                 // Index where the Key is found!

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.