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.

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.

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

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.

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.