struct Solution;

impl Solution {
    pub fn find_min(nums: Vec<i32>) -> i32 {
        Self::helper(&nums, 0, nums.len() -1)
    }

    fn helper(nums: &Vec<i32>, s: usize, e: usize) -> i32 {
        if s == e { return nums[s]; }
        if s + 1 == e { return nums[s].min(nums[e]); }

        if nums[s] < nums[e] { return nums[s]; }

        let mid = (s + e) / 2;
        if nums[mid] > nums[e] {
            return Self::helper(nums, mid, e);
        }

        if nums[s] > nums[mid] {
            return Self::helper(nums, s, mid);
        }

        0
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_find_min() {
        let nums = vec![3,4,5,1,2];
        let res = Solution::find_min(nums);
        assert_eq!(res, 1);
    }
}