Monthly Archives: April 2014

Searching an Element in a Rotated Sorted Array

What is Rotated Sorted Array
It is nothing but a sorted array, which is twisted/rotated with some pivot element.
So if you observe rotated array then it can be classified as two sub-array that is sorted.

For example your sorted array A:
A = { 0,1,2,3,4,5,6,7,8,9 }
and your rotated sorted array look like this:
A = { 2,3,4,5,6,7,8,9,0,1 }

Now how do you find an element in the rotated array efficiently? You may assume no duplicate exists in the array.

Continue reading