[swift-evolution] [Review] SE-0074: Implementation of Binary Search functions

Daniel Vollmer lists at maven.de
Wed May 11 10:10:23 CDT 2016

> On 10 May 2016, at 19:36, Joe Groff via swift-evolution <swift-evolution at swift.org> wrote:
> I worry that attaching these methods to a strongly-typed `Sorted` wrapper limits their appeal. It's useful to be able to binary-search through data in a standard container that's known to be sorted, or over a subregion of the data that's sorted. While you can of course cobble together a Sorted(Slice(container[sortedRange])), that's pretty inconvenient. Is misapplying binary search algorithms to unsorted data a big problem in practice in C++?

I agree with Joe here, just look at the recursive construction of a kd-tree where you recursively sort (and then search for a partitioning point) in smaller and smaller slices sorted along different dimensions.

I don’t think misapplying is a big problem in C++.


More information about the swift-evolution mailing list