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

*From*: "Pascal J. Bourguignon" <pjb@xxxxxxxxxxxxxxxxx>*Date*: Sun, 19 Dec 2010 01:29:50 +0100

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 {}.

.

**References**:**A log(n) search algorithm on an unsorted array***From:*perditi0n2002

**Re: A log(n) search algorithm on an unsorted array***From:*Ben Bacarisse

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

**Re: A log(n) search algorithm on an unsorted array***From:*Pascal J. Bourguignon

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

**Re: A log(n) search algorithm on an unsorted array***From:*Pascal J. Bourguignon

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

- Prev by Date:
**Re: A log(n) search algorithm on an unsorted array** - Next by Date:
**Re: A log(n) search algorithm on an unsorted array** - Previous by thread:
**Re: A log(n) search algorithm on an unsorted array** - Next by thread:
**Re: A log(n) search algorithm on an unsorted array** - Index(es):