Currently we have ImmutableVector::bsearch() and ImmutableOrdVector::bsearch_elem(), which uses binary search to find an element (I’ll use the term *needle* in the following post). It returns None if the needle is not found.

The problems:

**1)** The major problem is that often we would like to know the smallest index of an object “just next to” the needle, to establish a limit / threshold etc.

```
let container_sizes = [
("small", 20i),
("medium", 35),
("large", 75),
("huge", 120),
];
let smallest_container_index =
container_sizes.bsearch(|&(_, i)| i.cmp(&40));
println!("{}", smallest_container_index);
// Wants to get index of "large", got None instead which provides no
// information.
```

**2)** And a minor annoyance is that when there is a range of values equals to the needle, it’s unspecified which one will be returned:

```
let a = [1i, 2, 2, 2, 2, 2, 2, 2, 3];
println!("{}", a.bsearch_elem(&2));
// Currently prints Some(4), but anything from Some(1) to Some(7) may
// be possible.
```

In C++ we solve these tasks with `std::upper_bound`

and `std::lower_bound`

. Similarly we have `bisect.bisect_left`

and `.bisect_right`

in Python.

There are several ways to implement this. The most obvious way is to directly port the C++ method signatures into Rust:

```
/// Returns the smallest index `i` in `self` such that `f(self[i])`
/// is Greater or Equal.
///
/// If `f` is Less for all elements, this method returns `self.len()`.
fn lower_bound(&self, f: |&T| -> Ordering) -> uint;
/// Returns the smallest index `i` in `self` such that `f(self[i])`
/// is Greater.
///
/// If `f` is Less or Equal for all elements, this method returns
/// `self.len()`.
fn upper_bound(&self, f: |&T| -> Ordering) -> uint;
```

and the following methods to ImmutableOrdVector trait:

```
fn lower_bound_elem(&self, t: &T) -> uint;
fn upper_bound_elem(&self, t: &T) -> uint;
```

(I believe `bsearch()`

can then be implemented in terms of `lower_bound()`

in the trait, but I can’t make the compiler happy about the moved function yet.)

Suggestions?