Serving the Quantitative Finance Community

 
User avatar
tristanreid
Topic Author
Posts: 5
Joined: May 12th, 2004, 6:58 pm

programming teasers - Part 2 -- Sort and Search

July 7th, 2005, 8:24 pm

Alright, this one is MUCH less time consuming than 'part 1'. It's actually a problem that I vaguely remember from computer science in school, way back when. To keep it from being too tedious, just describe an algorithm, don't bother proving that it's O(log n), which should be obvious anyway.If you have a sorted array (call it A) you can find any element by using a binary search with O(log n) time. I take an empty array (B) of the same length (call the length 'L')I assign each element i of my new array as B's Ith element = A[(i+X)%L], where you don't know X. The % is the mod operator. I previously used standard array notation, but it makes the rest of the post italicized so I took it out.In other words, we're rotating the array by some unknown amount.Can you find an element in B in O(log n) time?Keep in mind, you know that the array is sorted, but the contents are not necessarily uniform.-t.
Last edited by tristanreid on July 6th, 2005, 10:00 pm, edited 1 time in total.
 
User avatar
mattcushman
Posts: 0
Joined: July 14th, 2002, 3:00 am

programming teasers - Part 2 -- Sort and Search

July 8th, 2005, 1:44 pm

You can find the value of X in O(log N) time (essentially a binary search, you keep narrowing down the position by a factor of 2 with each test by starting with a=1, b=N, so x(a)>x(b) [unless X=0] and bisect). From there, you can use a plain vanilla binary search, also O(log N).