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.