Search an element in a sorted and rotated array

An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, [ 1, 2, 3, 4, 5 ] might become [ 3, 4, 5, 1, 2 ]. Devise a way to find an element in the rotated array in O(log n) time.

Example

For inputs arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3} and key = 3 the correct answer is 8.
For inputs arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3} and key = 30 the correct answer is -1.
For Inputs arr[] = {30, 40, 50, 10, 20} and key = 10 the correct answer is 3.

Contributed by Murat Sütunç