Divide and conquer approach in search for max element

Question

Continuing the Algorithm in a Nutshell series, here is the code:

trait MaxElem<T> {
    fn max_elem<'a>(&'a self) -> &'a T;
}

impl<T> MaxElem<T> for Vec<T> where T: PartialOrd {
    fn max_elem<'a>(&'a self) -> &'a T {
        max_elem_helper(self, 0, self.len())
    }
}


fn max_elem_helper<'a, T>(vec: &'a Vec<T>, left: usize, right: usize) -> &'a T 
    where T: PartialOrd
{
    if right - left == 1 {
        return &vec[left];
    }
    let mid = (left + right) / 2;
    let max1 = max_elem_helper(vec, left, mid);
    let max2 = max_elem_helper(vec, mid, right);
    if max1 > max2 {
        max1
    } else {
        max2
    }
}

#[cfg(test)]
mod test {
    use max_elem::MaxElem;
    #[test]
    fn test_max_elem() {
        let vec = vec![11, 2, 9, 1, 3, 88]; 
        let m = *vec.max_elem(); 
        assert_eq!(m, 88);
    }
}

It's a simple algorithm that divide a vector into two parts and recursively search for the maximum.

All suggestions are welcome.

Answer 1

First of all I'm not sure why you use a divide and conquer approach here, given that just walking over the entire list once and getting the maximum element is both shorter and more efficient.

Secondly I would use the more general &[T] instead of &Vec<T>.

Your implementation will recurse forever and crash with a stack overflow when the input is empty.

Because you demand PartialOrd rather than Ord, the result you get from max_elem will depend on the order of the list. For instance, a list with floating point numbers may get inconsistent results when NaN is present: if the list ends with NaN then than will be the maximum element. If it begins with NaN but also contains other numbers, then a different number will be the maximum element. It is even possible for NaN to hide the maximum number, and make the method return a number that is not the largest. A demonstration:

fn show(v: Vec<f64>) { 
    println!("Max element of {:?} is {}", v, v.max_elem());
}
show(vec![1.0, std::f64::NAN]); // the max is NaN
show(vec![std::f64::NAN, 1.0]); // the max is 1
show(vec![10000.0, std::f64::NAN, 1.0, 1.0]); // the max is 1

Basically you should just use .iter().max() when you want the maximum element of some iterable structure, which avoids all of these problems.