Pre-RFC: More general binary search

I have implemented binsearch for &[T] which has a number of advantages over the existing binary_search method in primitive type slice. It can be presently seen in trait Vecops in my crate indxvec, version. 1.3.1.

  • It only requires PartialOrd instead of Ord.
  • It works on both ascending and descending orders, at the cost of a single test of an extra boolean argument specifying the order.
  • It always succeeds, i.e. it does not return Err. The std version uses Err mechanism to deliver a genuine sort-order result, which is arguably not quite right.
  • It always returns an unambiguous result: Range from the sort position of the first occurrence of the sought value till the last. Empty range n..n, means that the item was not found and n is its insert position. This mechanism is logically consistent and avoids doing Error processing of useful results.
  • It solves the sub-optimality hinted at in the documentation: " If there are multiple matches, then any one of the matches could be returned. The index is chosen deterministically, but is subject to change in future versions of Rust."

I am well aware that there is extreme reluctance to introduce changes to std but a breaking change could be avoided by simply adding this method for some transitional period.

Is this a useful RFC?

The thing you'd need for this is an API Change Proposals - Standard library developers Guide.

(It's not something with enough impact on the ecosystem to need a full RFC.)

These has been dealt with by partition_point, since you can use |x| x < a for PartialOrd if you want. (Or |x| x > a for a descending slice.)

The bar for a new type is quite high, and position+count is pretty unusual in rust.

But that has an easy solution: return Range<usize> instead. That still lets you return i..i if the place to insert it in sorted order is at i, and it's an existing type. It could even be used to index the original slice to get all the matching items.

Something like that has long been discussed under the name equal_range in Add `lower_bound`, `upper_bound` and `equal_range` for slices where T: Ord to complement `binary_search` · Issue #2184 · rust-lang/rfcs · GitHub

4 Likes

Thank you for that suggestion. I can certainly do that without any difficulty. And then retrieve the index from: range.start

Edit: Implemented now in indxvec v. 1.3.3 source

Thanks. Following your advice, I have now submitted it as an API change proposal.

(Link to the ACP, if anyone else is curious.)