I just found out about this library while browsing through Apple's GitHub site for SwiftNIO. I was doing this to take a break from... writing algorithms! In fact, I did binary search and sort check. What about this interface:
extension Sequence {
/// Returns a sequence containing the longest prefix of elements that are
/// sorted according to the given predicate.
public func sortedPrefix(stopsAtDuplicate: Bool = false, by areInIncreasingOrder: (Element, Element) throws > Bool) rethrows > [Element]
/// Returns a sequence formed by skipping the longest prefix of elements that
/// were sorted according to the given predicate.
public func dropSortedPrefix(stopsAtDuplicate: Bool = false, by areInIncreasingOrder: (Element, Element) throws > Bool) rethrows > PrependedIteratorSequence<Iterator>
}
extension Collection {
/// Returns the pasttheend index for the longest prefix of the collection
/// that can be considered sorted according to the given predicate.
public func sortedPivot(stopsAtDuplicate: Bool = false, by areInIncreasingOrder: (Element, Element) throws > Bool) rethrows > Index
}
All three have a variant the drops the predicate to default it to <
. The PrependedIteratorSequence
type carries over a dropped suffix and the element just before it, since I can't test where a sort breaks without reading the first postsort element from the iterator. (The standard DropWhileSequence
does the same thing.)
In sorting, runs of the same value are OK. But I added an optional flag for strictly increasing sequences/collections, for advanced work.
extension Collection {
/// Returns the index of some element equivalent to the given value,
/// assuming the collection is (at least) partially sorted according to the
/// given predicate.
public func someIndex(of element: Element, by areInIncreasingOrder: (Element, Element) throws > Bool) rethrows > (index: Index, isMatch: Bool)
/// Returns the index of the earliest element whose order is equivalent to
/// the element at the given index, assuming the collection is (at least)
/// partially sorted according to the given predicate.
public func lowerBound(for pivot: Index, by areInIncreasingOrder: (Element, Element) throws > Bool) rethrows > Index
/// Returns the index of the earliest element whose order is greater than
/// the element at the given index, assuming the collection is (at least)
/// partially sorted according to the given predicate.
public func upperBound(for pivot: Index, by areInIncreasingOrder: (Element, Element) throws > Bool) rethrows > Index
/// Returns the range of indices for the elements of the collection that are
/// all equivalent to the given value, assuming the collection is (at least)
/// partially sorted according to the given predicate.
public func sortedBounds(of element: Element, by areInIncreasingOrder: (Element, Element) throws > Bool) rethrows > Range<Index>
}
All four have a variant that removes the predicate parameter to default it to <
. I was inspired by the analogous functions from C++, but tried to improve their efficiency.

binary_search
just tells you if a match exists or not. It doesn't tell you where it is (if successful) or the best place to insert (if failure). Common implementations also just punt the work to lower_bound
. The someIndex(of: by:)
method gives you both the location (so you can do further work), and whether it's a match (so you don't need to test for endIndex
and for element equality before the main work) with a custom algorithm.
 Speaking of a custom algorithm,
someIndex(of: by:)
, lowerBound(for: by:)
, and upperBound(for: by:)
do separate parts of the process, and so have slightly different algorithms. Like I said, unlike C++, someIndex
never punts to lowerBound
, so it's free to stop at any match, even in the middle. If you want the lower border, you must explicitly ask for it.

binary_search
, lower_bound
, and upper_bound
base their searches off a value. While someIndex
does the same thing, lowerBound
and upperBound
work off a knowngood matching index. This is for efficiency; you have to call someIndex
or your own substitute first. And there's no need to worry about what happens if you use lb
or ub
with a nonexistent value; you couldn't get a matching index to use in the first place.

sortedBounds(of: by:)
calls the other three methods for a basic user interface.