add lower_bound and upper_bound to slice to complement binary search

[matiu2]

In the case where we do a binary search on an iterator and have a lot of keys the same, I'd like to find the first key and the last key, rather than a random key (what binary_search currently returns).

In c++ they have upper_bound and lower_bound, that will return the first and last of a block of duplicate keys.

Could we add these to slice too please ?

• upper_bound
• upper_bound_by_key
• upper_bound_by
• upper_bound_by_cached_key

(and all that again for lower bound)

[ExpHP]

And here is where it's unfortunate that binary_search returns Result<usize, usize> rather than some kind of expression object BinarySearch<'a, T> that could provide lower_bound() and upper_bound() methods.

[ExpHP]

A note: I think upper_bound should return the index after the last match.

[scottmcm]

This looks like a match for rust-lang/rfcs#2184, so I'm going to close in favour of that.

[AngelicosPhosphoros]

You can easily emulate this behaviour using binary_search_by: https://stackoverflow.com/a/75790348/8195987