[swift-dev] SequenceType Binary Search Implementation

[Dmitri Gribenko]

On Fri, Mar 11, 2016 at 8:11 AM, Lorenzo Racca via swift-dev
<swift-dev at swift.org> wrote:
> Now I don’t know whether this would be accepted, useful or just even right.
> I don’t have the permission to pull commits to the rep, so I don’t even
> really know how to make it an official proposal.

Hi Lorenzo,

The absence of binary searches is a known blank spot in the library,
and I'm glad that you are interested in fixing this.

We have a bug that tracks this issue: https://bugs.swift.org/browse/SR-368

Since this is an API change, we need to follow the Swift evolution
process [1].  I would appreciate if you could lead the conversation!
The way to word the initial email would be to present the proposed API
(not the implementation), and doc comments that explain the semantics.

Some specific advice for designing this API:

- Please familiarize yourself with C++ binary_search, lower_bound,
upper_bound, and equal_range APIs.  I'm not saying that these are the
best APIs for Swift, but these specific formulations have proven to be
useful in C++.

- Make sure you have overloads for 'Generator.Element : Comparable'
case as well as unconstrained overloads, where the comparison
predicate is supplied as a function parameter.

- Think about returning an boolean flag, returning the element, and
returning the element's index.  Which is the most primitive one that
others can be built on top with?  Which ones do we need to make
commonly-written code read well without extra complexity?

[1] https://github.com/apple/swift-evolution/blob/master/process.md

Thank you for tackling this problem!

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/