[pre-rfc] bind binary_search to traits instead of slice



binary_search is only available for slices. Sometimes the data is not convertible to a slice, but traits could be implemented.


It would be nice to enable core features like the binary_search algorithm on the data by just implementing the required traits.

Detailed design

The traits for binary_search would need random access to the elements (core::ops::Index) and the length (is there a trait?)

Currently a custom binary search implementation would be required, if the data structure is not convertible to a slice.

Like mentioned below, these could be grouped like in D, into something like a SortedRange Trait.


This does not necessarily need to be part of the rust core. It could also be moved to a separate crate. Although it is nice to have reliable methods in the core libraries.


You also need the elements to be sorted. See the SortedRange in D language.


Yes, but from the language perspective there is probably not much we could do about that, except bundle methods like binary_search into something like a SortedRange trait?


IIRC, the main thing holding stuff like this back are generalized collection traits and the main reason we don’t have those is the lack of HKT.

See the following for a relevent discussion (it doesn’t explicitly mention binary search but that would probably be added to the SortedSet trait):