[Proposal] Add Array binary search to the standard library

Evolution Discussion
1

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.

Best regards,
Cihat

2

Hi Cihat,

Thanks for diving in here! For reference, here's the last thing I said
about this topic (IIRC):

https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html

Also
https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679

Note: the comment there isn't quite right: <https://github.com/apple/swift/pull/7135&gt;

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)

Sounds consistent with my feedback... but it doesn't conform to
RandomAccessCollection. Why not?

- have a method that can find an object using binary search (solution: the index method)

Please see the algorithms prototype

- allow partitioning the array into smaller parts (solution: subscript, prefix & suffix methods)

* The collection returned by the slicing subscript should obey the law

     a[i..<j][i] == a[i]

  Normally that means you want to make it a different type from a.

- prevent re-implementing the Array class (solution: a getter to the
  stored internal array)

Not sure I understand what this is supposed to mean.

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.

Actually no, those are RangeReplaceableCollection 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.

You are right not to support MutableCollection or
RangeReplaceableCollection, as those would allow you to violate the
“sorted” invariant. However, it should conform to
RandomAccessCollection; that's really easy to implement and would
improve ease-of-use a lot.

···

on Sun Jan 29 2017, Cihat Gündüz <swift-evolution@swift.org> wrote:

Maybe my approach can somehow help forming the final solution to be
included into Swift once this features is tackled again.

Best regards,
Cihat
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
-Dave