Continuing the discussion from An always-sorted set:

I just updated the gist to Revision 2, which updates the "BinarySearch.swift" file. I did a rough search on this forum and found:

- [Discussion] Binary search, lower bound, upper bound, equal range
- SequenceType Binary Search Implementation
- [Proposal] Add Binary Search functions to SequenceType
- [Review] SE-0074: Implementation of Binary Search functions
- [Rejected] SE-0074: Implementation of Binary Search functions
- [Proposal] Add Array binary search to the standard library
- [Proposal] Add Array binary search to the standard library
- [Proposal] Add Array binary search to the standard library

The sequence/collection types were different back then, but I hope my interpretation works nowadays.

Instead of returning `false`

or `nil`

if a binary search fails, I return where that element value should go if you want to insert it into the collection (if its type included `RangeReplaceableCollection`

). I now realize that this is like the C++ `std::upper_bound`

function. From the old posts, I created a `partitionIndex(by:)`

function that generalizes the binary search. It uses the same kind of predicate as `MutableCollection.partition(by:)`

. It is used by `firstIndexOfSorted(exceeding: by:)`

, and both are moved from `RandomAccessCollection`

to `Collection`

, where the computation costs becomes O(n) except for random-access, where it's O(log n), where *n* is the collection length.

When the collection elements are `Comparable`

, a `firstIndexOfSorted(exceeding:)`

method is added for the common case that `<`

is the predicate.

Reading about the C++ `std::equal_range`

function, I made an equivalent `indicesOfSorted(for: by:)`

method that returns a `Range<Index>`

. An analogue of the C++ `std::binary_search`

can be done by checking if the range returned is not empty, while an analogue of `std::lower_bound`

and alternate for `std::upper_bound`

can be calculated by checking a bound of the returned range. There is a `Comparable`

optimization in `indicesOfSorted(for:)`

.

Right before writing those, I realized we could make a method that searches for a zone of element values. It's still the dual partition check, but the partition bounds now differ. It's the `indicesOfSorted(over:)`

method.