rust - 如何对 float 的 Vec 进行二分查找？

Question

如果你有一个 Vec<u32>你会使用 slice::binary_search 方法。

由于我不明白的原因，f32和 f64不实现 Ord .由于原始类型来自标准库，因此您无法实现 Ord在他们自己身上，所以看起来你不能使用这种方法。

您如何有效地做到这一点？

我真的必须包装f64吗？在包装器结构中并实现 Ord在上面？必须这样做似乎非常痛苦，并且涉及大量 transmute毫无理由地不安全地来回转换数据 block 。

Answer 1

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

因为 floating point is hard !简短的版本是 float 有一个特殊的值 NaN - Not a Number。 float 的 IEEE 规范指出 1 < NaN , 1 > NaN , 和 NaN == NaN都是false .

Ord 说:

Trait for types that form a total order.

这意味着比较需要具有完整性:

a ≤ b or b ≤ a

但是我们刚刚看到 float 没有这个属性。

所以是的，您将需要创建一个包装器类型，以某种方式处理比较 large number of NaN values .也许你的情况你可以断言浮点值永远不是 NaN 然后调用常规 PartialOrd 特征。这是一个例子:

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