On Sun, 19 Dec 2010, Ralph Boland 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.

It's not easy to do it right. The best would be to implement 
#indexOf:startingAt:ifAbsent:, because that's sent from #includes:.
To avoid code duplication you can reuse #indexForInserting: or use
#findBinaryIndex:ifNone:, but both of them is insufficient for a complete 
solution. You have to implement an additional galloping binary search to 
guarantee O(log(n)) runtime.


Levente

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