[swift-evolution] [Proposal] Add Array binary search to the standard library

[Dave Abrahams]

on Wed Sep 07 2016, Xiaodi Wu <swift-evolution at swift.org> wrote:

> Hi Igor,
>
> Since your proposal would be additive, it probably wouldn't be considered
> for review until the next phase of Swift evolution.
>
> My read of the core team's feedback is that some binary search
> functionality is welcome, but it's a question of *how* it's designed. When
> purely additive changes are in scope, a successful proposal will likely
> address the weaknesses of the previous proposal. Since that proposal
> considered as an alternative a design such as yours, but it concluded that
> a different design was better, you'll probably want to address why you
> think this API design is best, or alternatively, you may want to study the
> alternatives presented in that proposal and refine them to be better.

+1 to all that.  Also, this is not Array-specific; it applies to any
random-access collection at least, and arguably to any collection at
all.

> On Wed, Sep 7, 2016 at 05:16 Igor Vasilenko via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> do you mean this?
>>
>> public func binarySearch<T: Comparable>(array: [T], key: T, range: Range<Int>, sorted: Bool) -> Int?
>>
>> Best regards, Igor Vasilenko
>>
>> iOS Developer at Yota
>>
>> +7 (999) 527 - 07 - 59
>> spb.vasilenko at gmail.com <name.surname-nvfCEkAOCAdWk0Htik3J/w at public.gmane.org>
>> www.spbvasilenko.github.io <http://www.e-legion.com/>
>>
>>
>>
>>
>>
>>
>>
>>
>> On 07 Sep 2016, at 13:08, Guillaume DIDIER <
>> guillaume.didier.2014 at polytechnique.org> wrote:
>>
>> Basically for a binary search to work it needs to operate on a sorted
>> array (it is a necessary invariant).
>>
>> It is really interesting when you make a lot of search in the same sorted
>> array, hence I would +1 the sorted array, with initializer from an array.
>>
>>
>> *Guillaume  DIDIER*
>> —
>> *ÉCOLE POLYTECHNIQUE*
>> 91128 PALAISEAU CEDEX
>> M. +33 (0)7 70 43 18 40
>> guillaume.didier at polytechnique.edu
>> <guillaume.didier at polytechnique.edu?subject=>
>> www.polytechnique.edu
>> —
>>
>> Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution <
>> swift-evolution at swift.org> a écrit :
>>
>>
>> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>> Aside from this being additive (i.e. out of scope for Swift 4), this
>> requires the array to be sorted in order for the search to work - who will
>> guarantee this? The caller? What happens when this is called on an array
>> that is not sorted? You likely get nil, while the item is in the array
>> (false negative).
>>
>> This would probably make sense by not extending Array itself, but
>> introducing SortedArray which would automatically keep its members sorted
>> instead - this way there would be a guarantee that the array is sorted and
>> the user won't have to deal with sorting the array. It would however be at
>> the cost of O(log N) for insertion…
>>
>>
>> I don't think this is really a problem, just needs to be clear that
>> behaviour is undefined if the array wasn't previously sorted (or not in the
>> same order).
>>
>> On this topic there was a previous proposal that was undergoing
>> refinements after being initially rejected, you can find it here:
>>
>> https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave