Re: A log(n) search algorithm on an unsorted array



On 12/18/2010 2:56 PM, perditi0n2002 wrote:
....
I tried looking at this as a binary search algorithm although since
there is nothing known about the sequence of numbers other than
that the first is even and the last is odd, I can't halve the search
with each iteration because I have no idea if to go left or right from
the middle.

Perhaps the most important piece of data is the reassurance that the
problem is solvable, in logarithmic time.

You are on the right general line but need to think a little less
literally about binary search. It gets its logarithmic time by halving
the size of the problem on each step.

You are given a length n array with first element even, last element
odd. You need to find a length 2 sub-array with first element even, last
element odd.

Patricia
.