假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1
示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

 

思路：

1.首先考虑到 遍历解法  O(n)

public int findMin(int[] nums) {
		if (nums == null || nums.length == 0)
			return -1;
		if (nums.length == 1) {
			return nums[0];
		}
		for (int i = 0; i < nums.length; i++) {
			if (i + 1 <= nums.length - 1 && nums[i] > nums[i + 1]) {
				return nums[i + 1];
			}
		}
		// 能走到这里 说明都满足 递增的序列
		return nums[0];
	}

2.利用二分进行改进

通过二分方法 nums[mid]如果小于nums[end] 说明mid到end该段递增 nums[mid]如果大于等于nums[end]， 说明start到mid这段递增  可以结合例子看

 

输入: [3,4,5,1,2]
输出: 1
示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

 

 

代码：

public int findMin(int[] nums) {
		if (nums == null || nums.length == 0)
			return -1;
		int start = 0, end = nums.length - 1;
		while (start < end) {
		 if (nums[start]<nums[end])   //该段递增
	                return nums[start];
			int mid = start + (end - start) / 2;
			if (nums[mid] >=nums[end]) {
				start = mid + 1; // 向右缩小
			} else if (nums[mid] < nums[end]) {
				end = mid; // 向左缩小
			} 
		}
		return nums[start];
	}