Problem

For a provided vector of numbers vec we need to find the peak element. The peak element is an element that is greater or equal to its neighbors. If there are multiple peak elements in the vector, we can return any of them as the solution.

Examples:

Solution

fn find_peak_number(vec: &Vec<i32>) -> i32 {
    fn find_peak(v: &Vec<i32>, left: usize, right: usize) -> i32 {
        match (left + right) / 2 {
            // if mid elem is greater than left and right neighbors, then we found peak elem:
            m if (m == 0 || v[m] >= v[m - 1]) && (m == v.len() - 1 || v[m] >= v[m + 1]) => v[m],
            // if elem to the left of mid is greater than mid, then search in the left sub-vec:
            m if m != 0 && v[m - 1] > v[m] => find_peak(v, left, m - 1),
            // otherwise, search in the right sub-vec:
            m => find_peak(v, m + 1, right),
        }
    }

    assert!(!vec.is_empty(), "the input vector must not be empty");
    find_peak(vec, 0, vec.len() - 1)
}

Explanation

One simple way to solve the puzzle is to use the idea inspired by the Binary search algorithm. Recursively, we find a middle index m = (left + right) / 2 and then there are 3 possible cases to process:

1. If the element at the middle index v[m] is greater than its neighbors (taking into account that there might not be a neighbor to the left or the right of m, if m is the first or the last element), then we found the peak element.

2. If the element to the left of m is greater than v[m], then we recursively search in the left sub-vector: find_peak(v, left, m - 1).

3. Otherwise, we recursively search in the right sub-vector: find_peak(v, m + 1, right).

Complexity

The time complexity of the solution is O(log n) (where n is the size of the input vector). The auxiliary space complexity is also O(log n) because we chose to have the recursive binary search implementation, which adds up stack space on every recursive call.

---

Rust Playground with this code