153. Find Minimum in Rotated Sorted Array Medium

1/**
2 * [153] Find Minimum in Rotated Sorted Array
3 *
4 * Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
5 * 
6 * [4,5,6,7,0,1,2] if it was rotated 4 times.
7 * [0,1,2,4,5,6,7] if it was rotated 7 times.
8 * 
9 * Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
10 * Given the sorted rotated array nums of unique elements, return the minimum element of this array.
11 * You must write an algorithm that runs in O(log n) time.
12 *  
13 * Example 1:
14 * 
15 * Input: nums = [3,4,5,1,2]
16 * Output: 1
17 * Explanation: The original array was [1,2,3,4,5] rotated 3 times.
18 * 
19 * Example 2:
20 * 
21 * Input: nums = [4,5,6,7,0,1,2]
22 * Output: 0
23 * Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
24 * 
25 * Example 3:
26 * 
27 * Input: nums = [11,13,15,17]
28 * Output: 11
29 * Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 
30 * 
31 *  
32 * Constraints:
33 * 
34 * n == nums.length
35 * 1 <= n <= 5000
36 * -5000 <= nums[i] <= 5000
37 * All the integers of nums are unique.
38 * nums is sorted and rotated between 1 and n times.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
44// discuss: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn find_min(nums: Vec<i32>) -> i32 {
50        let (mut start, mut end) = (0, nums.len() - 1);
51        while start < end {
52            let mid = (end - start) / 2 + start;
53            if nums[mid] > nums[end] {
54                start = mid + 1;
55            } else {
56                end = mid;
57            }
58        }
59        nums[start]
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_153() {
71        assert_eq!(Solution::find_min(vec![3,4,5,1,2]), 1);
72        assert_eq!(Solution::find_min(vec![1]), 1);
73        assert_eq!(Solution::find_min(vec![1,2]), 1);
74    }
75}
76