Add binary_search_by for std::ops::Range

language design
1

Maybe we can add binary_search_by method to std::ops::Range so that we will have a more generic way to binary_search target.

Fox example, we can search a number in a sorted vec:

let n = sort_vec.len();
let result_index = (0..n).binary_search_by(|x| sort_vec[x].cmp(&target));

we can find the minimum / maximum value that satisfies the condition :

let condition = |x|{};//condition function to test value
let result = (0..1000000).binary_search_by(condition);

//there is a hack way to do this right now ,but collect is too slow
(0..1000000).collect::<Vec<_>>().binary_search_by(condition);

and so on

with the help of range.binary_search_by(), maybe we don't need to write binary_search by ourselves.

8 Likes
2

I just encountered this problem professionally in Python.

In my case the problem required searching the 'step' within a lazy binary list from False to True, but each element was very expensive to compute. With Python's bisect one can hack together a solution.

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

The module just assumes that a implements the list interface, it doesn't rely on it being an explicit list. Thus, one can pass any class implementing:

class ListLike:
    def __len__(self) -> int:
        pass
    def __getitem__(self, x: int):
        pass # Do expensive computation here

bisect.bisect_left(ListLike(), True)

If begin..end is a sufficient replacement for all parameters above (hi or lo are mostly for convenience, and the length can be compted from the interval) then this yields pretty much the proposed interface except for the search parameter x.

This could be three concrete methods that already have analogues in slice

impl Range<usize> {
    fn binary_search_by(self, FnMut(usize) -> Ordering);
    
    // Convenience, maybe?
    fn binary_search(self, x: &T, FnMut(usize) -> &T);
    fn binary_search_by_key<T>(self, x: &T, FnMut(usize) -> T);

    // Convenience, definitely imho.
    fn partition_point<T>(self, FnMut(usize) -> bool);
}
2 Likes
3
1 Like
4

The prior art all seems to be about slices and data structures unless I missed something. A method on Range seems very elegant and widely applicable to me. I think it would be worth a PR and/or API Change Proposal.

5

I've wanted this before, and it is a strictly more general version of the existing binary search methods on slices, but implementing this may not be straightforward. Ranges over which types should get this functionality? The Step trait seems like a logical choice, but it does not provide a reasonable way for integer types larger than usize to find the midpoint between two given values.

Of course, only implementing it for Range<usize> is just a matter of taking the existing binary search code on slices and making some very minor modifications.

1 Like
6

The linked ACP discussion veered towards a generalized binary search that would also work on ranges.

The linked crate does have a Trait that can be implemented on anything that can be mapped to searchable indices.

7

I like this idea, but I think bisect would be a better name than binary_search_by.

On the question which ranges should have this method, I think it should be implemented for Range<T>, where T implements an unstable Bisect trait:

trait Bisect: Step {
    fn midpoint(min: Self, max: Self) -> Self;
}
8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.