on Wed Sep 07 2016, Xiaodi Wu <[email protected]> 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 < > [email protected]> 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 >> [email protected] >> <name.surname-nvfCEkAOCAdWk0Htik3J/[email protected]> >> www.spbvasilenko.github.io <http://www.e-legion.com/> >> >> >> >> >> >> >> >> >> On 07 Sep 2016, at 13:08, Guillaume DIDIER < >> [email protected]> 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 >> [email protected] >> <[email protected]?subject=> >> www.polytechnique.edu >> — >> >> Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution < >> [email protected]> a écrit : >> >> >> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution < >> [email protected]> 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 >> [email protected] >> https://lists.swift.org/mailman/listinfo/swift-evolution >> >> >> >> _______________________________________________ >> swift-evolution mailing list >> [email protected] >> https://lists.swift.org/mailman/listinfo/swift-evolution >> > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution > -- -Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
