Showing posts with label Binary Search. Show all posts
Showing posts with label Binary Search. Show all posts

Saturday, 9 November 2013

Searching an Element in Rotated Sorted Array

One of my friend was ask to devise an algorithm to search a number on a rotated sorted array. Well, we can always do a linear search. But that cannot be optimal we are neglecting the fact that the array was once sorted. The array is still sorted but has been rotated at some point. So, if we could find the rotation point, we could still use binary search to find the number.