Subj : Re: rotated sorted list search
To   : comp.programming
From : CBFalconer
Date : Mon Aug 15 2005 05:33 pm

JD wrote:
> 
> An element in a sorted array can be found in O(log n) time via
> binary search. But suppose I rotate the sorted array at some pivot
> unknown to you beforehand. So for instance, 1 2 3 4 5 might become
> 3 4 5 1 2. Now devise a way to find an element in the rotated
> array in O(log n) time

You should be able to find the pivot with a modification of the
binary search method in O(log n) time.  Then the problem reduces to
the original.


-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson

.