Java: Search an Element in a Sorted and Rotated Array

Difficulty Level: MEDIUM

Problem Statement:

Given a sorted and rotated array arr[] of size N and a key, the task is to find the key in the array.

Note: Find the element in O(logN) time and assume that all the elements are distinct.

Input:

arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, Key = 9

Output:

Found at index 4