算法题解2_求连续子数组的最大和

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1

解法

最直观的解法并不难，从头到尾遍历一次就行，但是这样就太low了。直观上应该用二分法 low，middle，high。如果 middle > low，说明middle仍然在前半部分，则令low = middle；如果middle < high，说明middle在后部分，另high = middle

代码如下：

public static int min(int[] nums) {
	
	if ( null == nums || 0 == nums.length )
		return -1;		// -1代表出错
	
	int low = 0;
	int high = nums.length - 1;
	int middle = low;
	while ( nums[low] >= nums[high] ) {
		
		if ( 1 == high - low ) {
			middle = high;
			break;
		}
		
		middle = (low + high) / 2;
		
		// 特殊情况
		if( nums[low] == nums[middle] && nums[middle] == nums[high] )
			return minInOrder(nums, low, high);
		
		if ( nums[middle] >= nums[low] ) 
			low = middle;
		else if ( nums[middle] <= nums[high] )
			high = middle;
	}
	
	
	return nums[middle];
}



private static int minOrder(int[] nums, int low, int high) {
	
	int min = nums[low];
	
	for (int i = low; i <= high; i++) {
		if ( nums[i] < min)
			min = nums[i];
	} 
	
	return min;
}


public static void main(String[] args) {
	
	
	int[] arr = {3, 4, 5, 1, 2};
	System.out.println( min(arr) );
}

注意这里的一个特殊情况： {1，0，1，1，1}和{1，1，1，0，1}都是{0，1，1，1，1}的旋转，但是不久后发现low，high，middle全部相等，这时候只能蛮力求解

Written on January 6, 2016