Subj : Re: rotated sorted list search To : comp.programming From : cri Date : Mon Aug 15 2005 04:10 pm On 15 Aug 2005 07:17:17 -0700, "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 Is this a homework problem or just something you've tossed out for people to play with? If it is a homework problem here's a hint - you can find the pivot in O(log n) time. Richard Harter, cri@tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate. .