Binary search in hash keys

[naktinis]

I'm trying to find the largest key of an ordered map that is smaller than some value. E.g. if keys were [2, 4, 6] and I'm looking for 5, then the result should be 4.

In "collections" module documentation BTreeMap is described as useful for this purpose:

Use a BTreeMap when:
...

• You want to find the largest or smallest key that is smaller or larger than something

However in BTreeMap documentation no such method is defined (unless I missed it). You can only iterate over all keys and look for it linearly yourself or collect all keys into memory as an array or vector and use binary search on it (there's a binary_search_by method that can be used on a slice). But that would be less efficient (and more cumbersome) than operating on the b-tree structure.

What is the right approach here and isn't the "collections" module documentation misleading?

[stebalien]

You can only do this in nightly currently:

map.range(Bound::Unbounded, Bound::Excluded(5)).rev().next()

[Gankra]

A better specific API is being discussed at

ordered query API

[benaryorg]

As I have already commented there, a builder pattern would be great.

@Gankro

I regard Bound as a necessary evil for range because the combinatorics there seem truly catastrophic (18 iterator methods). That said I've never been super happy with the range design. Someone once suggested a builder pattern to me like:

// unbounded RHS
.range().from(x).into_iter()
// bounded RHS
.range().from(x).to(y).into_iter()
// ...etc

Might be worth considering that more seriously.