Re: binary search

[Alexander Burger]

Hi Mike,

> Today I was wonder is it possible to create a function for binary search
> inside flatten or nested lists.
> If I have ordered list I need something faster that O(n) and I should not
> care of unique structure.
> It was a goal while walking in the forest.

You can do a binary search also in a linked list.

See e.g. the 'balance' function in @lib/misc.l (not a binary *search*,
but an analog processing).

♪♫ Alex
-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Re: binary search

[Joh-Tob Schäg]

Hi

have you thought about implementing a skip list?
It would be implemented very easily, it in particular excels with biased
queries (certain parts more often than others) and other interesting
properties, but has O(log(N)) access time, you could in theory even map
some functions (which do not change the ordering of the elements (- 13 (*
19 N)) vs mod 2 (You get the idea)) on the data, without rebuilding the
index.
I would use the value to store the data and write procedures which follow
the overhead stored in the property list. With little backtracking you
would not even need double link lists, even though they are often
implemented in this manner.

Sincerely
*freeemint_*



2016-01-17 20:13 GMT+01:00 Mike Pechkin :

> hi all,
>
> Today I was wonder is it possible to create a function for binary search
> inside flatten or nested lists.
> If I have ordered list I need something faster that O(n) and I should not
> care of unique structure.
> It was a goal while walking in the forest.
>
> There is my code in repo:
> https://goo.gl/EMQt3p
>
> Mike
>
>