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

Question

If you have a Vec<u32> you would use the slice::binary_search method.

For reasons I don't understand, f32 and f64 do not implement Ord. Since the primitive types are from the standard library, you cannot implement Ord on them yourself, so it does not appear you can use this method.

How can you effectively do this?

Do I really have to wrap f64 in a wrapper struct and implement Ord on it? It seems extremely painful to have to do this, and involves a great deal of transmute to cast blocks of data back and forth unsafely for effectively no reason.

Answer 1

One of the slice methods is binary_search_by, which you could use. f32/f64 implement PartialOrd, so if you know they can never be NaN, you can unwrap the result of partial_cmp:

fn main() {
    let values = [1.0, 2.0, 3.0, 4.0, 5.0];
    let location = values.binary_search_by(|v| {
        v.partial_cmp(&3.14).expect("Couldn't compare values")
    });

    match location {
        Ok(i) => println!("Found at {}", i),
        Err(i) => println!("Not found, could be inserted at {}", i),
    }
}

Answer 2

https://github.com/emerentius/ord_subset implements a ord_subset_binary_search() method that you can use for this.

from their README:

let mut s = [5.0, std::f64::NAN, 3.0, 2.0];
s.ord_subset_sort();
assert_eq!(&s[0..3], &[2.0, 3.0, 5.0]);
assert_eq!(s.ord_subset_binary_search(&5.0), Ok(2));

assert_eq!(s.iter().ord_subset_max(), Some(&5.0));
assert_eq!(s.iter().ord_subset_min(), Some(&2.0));

Answer 3

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);
}

Answer 4

If you are sure that your floating point values will never be NaN, you can express this semantic with the wrappers in decorum. Specifically, the type Ordered implements Ord and panics whenever the program tries to do something invalid:

use decorum::Ordered;

fn foo() {
    let ordered = Ordered<f32>::from_inner(10.);
    let normal = ordered.into()
}