1

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:

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.

1 Like