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

[Cihat Gündüz]

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:
https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift

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.

Best regards,
Cihat
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170129/3aad0210/attachment.html>