159. Find Minimum in Rotated Sorted Array 【medium】

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

Notice

You may assume no duplicate exists in the array.

Have you met this question in a real interview?

Yes

Example

Given [4, 5, 6, 7, 0, 1, 2] return 0

解法一：

 1 class Solution {
 2 public:
 3     /*
 4      * @param nums: a rotated sorted array
 5      * @return: the minimum number in the array
 6      */
 7     int findMin(vector<int> nums) {
 8         int start = 0;
 9         int end = nums.size() - 1;
10         
11         while (start + 1 < end) {
12             int mid = start + (end - start) / 2;
13             
14             //1 2 3 4 5 6
15             if (nums[mid] > nums[start] && nums[mid] < nums[end]) {
16                 end = mid;
17             }
18             // 3 4 5 6 1 2
19             else if (nums[mid] > nums[start] && nums[mid] > nums[end]) {
20                 start = mid;
21             }
22             // 5 6 1 2 3 4
23             else if (nums[mid] < nums[start] && nums[mid] < nums[end]) {
24                 //start = mid;
25                 end = mid;
26             }
27         }
28         
29         return nums[start] > nums[end] ? nums[end] : nums[start];
30     }
31 };

注意分数组的奇偶去考查。比如[1, 2, 3, 4, 5]和[1, 2, 3, 4, 5, 6]是不同的。

解法二：

 1 public class Solution {
 2     /**
 3      * @param nums: a rotated sorted array
 4      * @return: the minimum number in the array
 5      */
 6     public int findMin(int[] nums) {
 7         if (nums == null || nums.length == 0) {
 8             return -1;
 9         }
10         
11         int start = 0, end = nums.length - 1;
12         int target = nums[nums.length - 1];
13         
14         // find the first element <= target
15         while (start + 1 < end) {
16             int mid = start + (end - start) / 2;
17             if (nums[mid] <= target) {
18                 end = mid;
19             } else {
20                 start = mid;
21             }
22         }
23         if (nums[start] <= target) {
24             return nums[start];
25         } else {
26             return nums[end];
27         }
28     }
29 }

大神解法就是给力！