How to do a binary search on a Vec of floats?

by

for reasons I don’t understand, f32 and f64 do not implement Ord.

Because floating point is hard! The short version is that floating point numbers have a special value NaN – Not a Number. The IEEE spec for floating point numbers states that 1 < NaN, 1 > NaN, and NaN == NaN are all false.

Ord says:

Trait for types that form a total order.

This means that the comparisons need to have totality:

a ≤ b or b ≤ a

but we just saw that floating points do not have this property.

So yes, you will need to create a wrapper type that somehow deals with comparing the large number of NaN values. Maybe your case you can just assert that the float value is never NaN and then call out to the regular PartialOrd trait. Here’s an example:

use std::cmp::Ordering;

#[derive(PartialEq,PartialOrd)]
struct NonNan(f64);

impl NonNan {
    fn new(val: f64) -> Option<NonNan> {
        if val.is_nan() {
            None
        } else {
            Some(NonNan(val))
        }
    }
}

impl Eq for NonNan {}

impl Ord for NonNan {
    fn cmp(&self, other: &NonNan) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

fn main() {
    let mut v: Vec<_> = [2.0, 1.0, 3.0].iter().map(|v| NonNan::new(*v).unwrap()).collect();
    v.sort();
    let r = v.binary_search(&NonNan::new(2.0).unwrap());
    println!("{:?}", r);
}

More Related Contents:

  1. Why is it legal to borrow a temporary?
  2. How can I create my own data structure with an iterator that returns mutable references?
  3. Convert a String to int?
  4. How do I borrow a RefCell, find a key, and return a reference to the result? [duplicate]
  5. How can I store a Chars iterator in the same struct as the String it is iterating on?
  6. Converting from Option to Option
  7. How to disable unused code warnings in Rust?
  8. Is there a way other than traits to add methods to a type I don’t own?
  9. What is the difference between `e1` and `&e2` when used as the for-loop variable?
  10. Why doesn’t println! work in Rust unit tests?
  11. What does ‘let x = x’ do in Rust?
  12. Why is the `Sized` bound necessary in this trait?
  13. Is it possible to return either a borrowed or owned type in Rust?
  14. How do I overcome match arms with incompatible types for structs implementing same trait?
  15. Example of how to use Conditional Compilation Macros in Rust
  16. How can I call a raw address from Rust?
  17. Is there a way to perform an index access to an instance of a struct?
  18. How to use a local unpublished crate?
  19. Why do I get “type annotations needed” when using Iterator::collect?
  20. Why would I use divergent functions?
  21. How to generate statically linked executables?
  22. Why can I iterate over a slice twice, but not a vector?
  23. When is it necessary to circumvent Rust’s borrow checker?
  24. How to idiomatically alias a crate in Rust 2018?
  25. Cannot borrow immutable borrowed content as mutable
  26. Why do I get “does not live long enough” in a return value?
  27. Why does the compiler not complain that an iterator moved to a for loop is immutable?
  28. Removing items from a BTreeMap or BTreeSet found through iteration
  29. Why doesn’t the lifetime of a mutable borrow end when the function call is complete?
  30. How do I avoid unwrap when converting a vector of Options or Results to only the successful values?

Leave a Comment