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

• From: Patricia Shanahan <pats@xxxxxxx>
• Date: Sat, 18 Dec 2010 15:43:05 -0800

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
.

## Relevant Pages

• Re: LISP PROGRAMMING
... >> occuring at odd numbered position but keeps the elements at even ... The first element ... Tyler: "How's that working out for you?" ...
(comp.lang.lisp)
• Re: A log(n) search algorithm on an unsorted array
... would automatically make the runtime complexity longer than logso ... the first element is even, and the last is odd! ... Or it could be another unspecified order;-) ...
(comp.programming)
• Re: A log(n) search algorithm on an unsorted array
... would automatically make the runtime complexity longer than logso ... the first element is even, and the last is odd! ... the second half to find an even-odd pairing. ...
(comp.programming)
• Re: Numeric Maze (#60)
... On 12/30/05, James Edward Gray II ... >> halve (Odd numbers cannot be halved.) ... we use the original tranformations to get: ...
(comp.lang.ruby)