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



perditi0n2002 <hod.nadav@xxxxxxxxx> writes:

On Dec 19, 1:30 am, "Pascal J. Bourguignon" <p...@xxxxxxxxxxxxxxxxx>
wrote:
perditi0n2002 <hod.na...@xxxxxxxxx> writes:
Well yeah if it were sorted I could use binary search. But sorting it
would automatically make the runtime complexity longer than log(n) so
that's impossible.

But it IS sorted: the first element is even, and the last is odd!

--
__Pascal Bourguignon__                    http://www.informatimago.com/
A bad day in () is better than a good day in {}.

We have different interpretations of sorted I suppose. By sorted I
mean that every number is either definitely larger or definitely
smaller than the next. Or all even numbers are to one side of a
certain number and all odd numbers are to the other side. Something
definite. In this instance it wasn't initially apparent to me that if
your middle is an even number then certainly you should look towards
the second half to find an even-odd pairing.

Or it could be another unspecified order ;-)


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
.



Relevant Pages

  • 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: 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
    ... that the first is even and the last is odd, I can't halve the search ... problem is solvable, in logarithmic time. ... You are given a length n array with first element even, ...
    (comp.programming)