[squeak-dev] includes: does linear search for SortedCollection???????

Igor Stasenko siguctua at gmail.com
Sun Dec 19 17:52:30 UTC 2010


On 19 December 2010 18:11, Ralph Boland <rpboland at gmail.com> wrote:
> The main advantage of a sorted list is that binary search can be
> performed on the list.
> So I was surprised to find that the method SortedCollection>>includes:
> (actually OrderedColection>includes:) does a linear search (Squeaks
> 10.2 and 4.1).
>
> I suggest we implement a version of SortedCollection>>includes: that
> runs in O(log n)
> time.  I can write this if desired or just about anybody.
>
you can do binary search if argument can be passed to sort block and
respond to any message(s) which sort block sends to it for determining
its order.

and what you suppose to do with:
coll includes: nil

or any other argument, which can't be used for binary search?



> Regards,
>
> Ralph Boland
>
> --
> Quantum Theory cannot save us from the tyranny of a deterministic universe
> but it does give God something to do
>
>



-- 
Best regards,
Igor Stasenko AKA sig.



More information about the Squeak-dev mailing list