[swift-evolution] [Proposal] Add Array binary search to the standard library
cihatguenduez at posteo.de
Sun Jan 29 15:49:23 CST 2017
Hi guys, I know this topic is probably out of scope for Swift 4 and a proposal was already rejected for Swift 3, but I’d like to share my two cents on this as I just wrote a SortedArray class with support for binary search in my open source library HandySwift.
You can see my classes current implementation here:
My goal was to provide only what is commonly needed when working with big arrays in algorithms. For me this included:
- having a type that keeps a sorted array to prevent re-sorting (solution: the SortedArray class)
- have a method that can find an object using binary search (solution: the index method)
- allow partitioning the array into smaller parts (solution: subscript, prefix & suffix methods)
- prevent re-implementing the Array class (solution: a getter to the stored internal array)
Also note that the SortedArray in my approach allows all types that conform to `Sequence` as input with `Comparable` elements and saves them into a sorted array on initialization. That array is also publicly read-accessible. Inserting and deleting objects from the SortedArray are possible, too, but that’s just few of the MutableCollection methods. I didn’t want the SortedArray to conform to MutableCollection or even RandomAccessCollection as I felt it was not needed just to support binary search and prevent re-sorting.
Maybe my approach can somehow help forming the final solution to be included into Swift once this features is tackled again.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the swift-evolution