Stream: t-libs

Topic: Range::binary_search


Tim Vermeulen (Jan 11 2020 at 17:23, on Zulip):

I've long wanted to add a binary search to Range because of how useful binary search can be even without a slice, how could this best be approached?
It doesn't seem possible to use the Step trait in its current form for this, so I see a couple options:

simulacrum (Jan 11 2020 at 17:28, on Zulip):

What do you mean by binary search on range? What would you be searching in?

Tim Vermeulen (Jan 11 2020 at 17:39, on Zulip):

You'd be searching in the range itself. I should have been more specific, this only works with binary_search_by and binary_search_by_key, binary_search as it's currently on [T] would indeed make no sense

Tim Vermeulen (Jan 11 2020 at 17:42, on Zulip):

The signature of Range<usize>::binary_search_by would be

fn binary_search_by<F: FnMut(usize) -> Ordering>(&self, f: F) -> Result<usize, usize>

and using that [T]::binary_search_by could be reimplemented using something like (0..self.len()).binary_search_by(|i| f(self[i]))

kennytm (Jan 11 2020 at 17:49, on Zulip):

is it something like Go's sort.Search?

Tim Vermeulen (Jan 11 2020 at 17:56, on Zulip):

It does seem like it! The main difference being that by having the closure return an Ordering, the function is able to return Ok/Err depending on whether the search "succeeded"

Last update: Jul 02 2020 at 12:40UTC