[swift-evolution] [Discussion] Binary search, lower bound, upper bound, equal range

[Pyry Jahkola]

> On 16 Feb 2016, at 17:49, Jeff Hajewski <jeff.hajewski at gmail.com> wrote:
> 
> I wonder if we can loosen the restriction of conforming to RandomAccessIndexType.

Yay, it turned out simpler than I thought!

I added a performance test to make sure there's no regression on RandomAccessIndexType's performance, then simply downgraded the RandomAccessIndexType requirement to ForwardIndexType (and used != instead of < in a few places). The updated code <https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327> is in GitHub.

That appears to work because of protocol inheritance magic in the standard library. So, even though my search algorithm only knows about ForwardIndexType, whenever Index happens to implement O(1) versions of advancedBy(_:) and distanceTo(_:), then those get used instead of the O(N) default implementations (Index.swift <https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262> on the Swift repository). Cool!

There might still be place for improvement, since the internal use of midIndex still passes across the same index ranges several times during the search on ForwardIndexType. If I did my math right, the current implementation makes something like 3N index increments on ForwardIndexTypes, while probably at least 2N can be achieved without much memory use.

> I think maybe the Ordering enum should be broken out into a separate proposal since it's not currently part of the standard lib. That being said, it does make for a clean implementation.

You're absolutely right. I should also paint the bikeshed of naming its cases (.LT, .EQ, and .GT) less obscurely before officially proposing it to swift-evolution. Maybe either  .ascending, .equivalent, and .descending, or simply .less, .equal, and .greater. And I expect there to be resistance against adding yet another comparison operator, even if there's precedent on the use of something like "a <=> b" in several other languages.

— Pyry Jahkola
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160216/1626d6db/attachment.html>