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] <mailto:[email protected]?subject=> www.polytechnique.edu <http://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
