&Option<T> from &T

Question

So I have a struct with an array of keys and a method, in which I wanna do a binary search with the given key.

struct MyStruct<const N: usize, K: Ord> {
    keys: [Option<K>; N]
}

impl<const N: usize, K: Ord> MyStruct<N, K> {
    fn new() -> MyStruct<N, K> {
        MyStruct {
            keys: std::array::from_fn(|_| None)
        }
    }

    fn foo(&self, key: &K) {
        let key = Some(key);
        let _index = self.keys.binary_search(&key);
        // snip
    }
}

The binary_search(&key) doesn't work, because I don't have a &Option<K>. Is there a way to convert the key of type &K to an &Option<K>? Or is there another way to be able to call binary_search() with the given key?

I don't wanna put an &Option<T> as type for the parameter of foo, since foo(None) wouldn't make any sense, because the None values inside the array are just placeholders for entries, that are semantically out of bounds.

The only solutions I see here is making K: Ord + Default and have keys defined without the Option wrapper as [K; N], or K: Ord + Copy, so I be able to make key: K instead of key: &K. But it seems unnecessary to force the keys to be Default or Copy. If someone knows any other solution to this. please let me know :)

Answer 1

Since the key parameter is a reference, you won't be able to move the referenced value it points to in order to place it into an option (you could eventually clone it).

A workaround would be to use .binary_search_by() in order to express the comparison not on Option<K> but rather on Option<&K>, thanks to Option::as_ref(). You could also find .binary_search_by_key() easier.

    fn foo(
        &self,
        key: &K,
    ) {
        let opt_key = Some(key);
        let _index = self.keys.binary_search_by(|o| {
            o.as_ref().cmp(&opt_key)
        });
        // snip
    }

    fn foo(
        &self,
        key: &K,
    ) {
        let opt_key = Some(key);
        let _index = self.keys.binary_search_by_key(&opt_key, Option::as_ref);
        // snip
    }