Implement limit-based binary search on slice

[sicking]

The current binary_search_* API on slice is very flexible in that it both allows searching for items in the slice, as well as the ranges "between" the items.

However this flexibility comes at the cost in situations where the values in the array acts as limits, rather than items to search for. I.e. where you don't care if the searched for value falls between two items, or exactly on one of the items.

Specifically, to search for the first item greater than a given value neither solution below is particularly obvious or pleasant to type:

use std::cmp::Ordering::{Greater, Less}
slice.binary_search_by(|&x| if x > 5 { Greater } else { Less }).unwrap_err()
// or
slice.binary_search(&5).map(|x| x+1).unwrap_or_else(|x| x)

To search for the first item greater than, or equal to, a given value is easier but isn't an obvious modification from the above.

slice.binary_search(&5).unwrap_or_else(|x| x)

In both of these situations it felt easy enough to have off-by-one errors that I ended writing small test cases and manually testing all edge cases until I felt that I used the right math.

The problem is that in these situations both the returned type (Ordering) from the closure is a poor fit, since you really just have two different results (too small or too large). Additionally the return type from the the binary_search_* function isn't a good fit since you just need a usize.

I propose (and will attach a PR for) that we add a slice.binary_search_limit_by function directly returns a usize, and which takes a closure which maps from an item to a bool in order to do the search.

We should probably also add slice.binary_search_limit which finds the first item larger than (or larger than or equal to) the given value, as well as slice.binary_search_limit_by_key which does the same using a key mapping function. Unfortunately these feel a bit more awkward since we have to choose if these do a "find first item larger" or a "find first item larger or equal" search.

I'm not sure if this change is large enough or controversial to require an RFC?

[sicking]

This might also be able to provide a small performance benefit for these use cases since I think we can skip the last couple of lines in the current binary_search_by implementation. Though the attached PR doesn't take advantage of that in an effort to reduce code duplication.

[sicking]

An alternative solution for slice.binary_search_limit and slice.binary_search_limit_by_key would be to make the limit argument be of type std::ops::Bound<T>. So

slice.binary_search_limit(Included(&5))

would return the first value >= 5 and

slice.binary_search_limit(Excluded(&5))

would return the first value > 5. Same thing for binary_search_limit_by_key. One downside would be what to do for

slice.binary_search_limit(Unbounded)

Most likely returning 0 would be the right thing to do, but panicking could also be an option.

[scottmcm]

Cross-linking Add lower_bound, upper_bound and equal_range for slices where T: Ord to complement binary_search, rust-lang/rfcs#2184

Are Included and Excluded not just lower_bound and upper_bound?

[sicking]

Are Included and Excluded not just lower_bound and upper_bound?

Yes they are the same.

lower_bound_by is not quite the same as binary_search_limit_by though. lower_bound_by basically sit between binary_search_limit_by and binary_search_by in terms of functionality.

[Amanieu]

This has been solved by the partition_point API.