【剑指offer】 面试题8： 旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

九度 ： http://ac.jobdu.com/problem.php?pid=1386

不知道为什么一直超时。

package com.offer.chapter_2;

import java.util.Scanner;

/**
 * @author hadoop
 *	
 *  把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，
 *  输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
 *  
 */
public class Interviews_8 {
	
	public static int findMinData2(int[] data, int start, int end) {
		// 只有一个元素
		if(start == end) {
			return data[start];
		} 
		
		// 只有两个元素
		if(end - start == 1) {
			return data[start] < data[end] ? data[start] : data[end];
		}
		
		// 没有旋转情况
		if(data[end] > data[start]) {
			return data[start];
		}
		// 至少三个元素
		int mid = (start + end) >> 1;
		// 当前中间元素小于前一个元素
		if(data[mid] < data[mid - 1]) {
			return data[mid];
		} else {
			// 当前中间元素大于第一个元素
			if(data[mid] > data[start]) {
				return findMinData(data, mid + 1, end);
				// 当前中间元素小于第一个元素	
			} else if(data[mid] < data[start]) {
				return findMinData(data, start, mid - 1);
			} else {
				// 当前中间元素等于第一个元素
				// 当大于三个数且data[mid] == data[start] 且前提 data[mid] >= data[mid - 1]
				// 1、最小值在前面 3 1 2 3 3 3 3 3 
				// 2、最小值在后面 3 3 1 2
				// 当前中间元素大于最后一个元素
				
				// 该方法不可行
				// 3 1 2 3 3 3 3 3 3 3 3 3 始终不能断定在哪一边
				if(data[mid] > data[end]) {
					return findMinData(data, mid + 1, end);
				} else {
					return findMinData(data, start, mid - 1);
				}
			}
		}
	}
	
	public static int findMinDataInOrder(int[] data, int start, int end) {
		int min = data[start];
		for(int i= start + 1; i<=end; i++) {
			if(data[i] < min) {
				min = data[i];
			}
		}
		return min;
	}
	
	public static int findMinData(int[] data, int start, int end) { 
		// 只有一个元素
		if(start == end) {
			return data[start];
		} 
		
		// 只有两个元素
		if(end - start == 1) {
			return data[start] < data[end] ? data[start] : data[end];
		}
		
		// 没有旋转情况
		if(data[end] > data[start]) {
			return data[start];
		}
		// 至少三个元素
		int mid = (start + end) >> 1;
		
		if(data[start] == data[end] && data[start] == data[mid]) {
			return findMinDataInOrder(data, start, end);
		}
		
		if(data[mid] < data[mid -1]) {
			return data[mid];
		} else {
			if(data[mid] > data[start]) {
				return findMinData(data, mid + 1, end);
			} else {
				return findMinData(data, start, mid -1);
			}
		}
	}
	
	public static int findMinData3(int[] data) {
		int start = 0;
		int end = data.length - 1;
		int mid = start;
		
		while(data[start] >= data[end]) {
			if(end - start == 1) {
				mid = end;
				break;
			}
			
			mid = (start + end) >> 1;
			if(data[start] == data[end] && data[start] == data[mid]) {
				return findMinDataInOrder(data, start, end);
			}
			
			if(data[mid] >= data[start]) {
				start = mid;
			} else if(data[mid] <= data[end]) {
				end = mid;
			}
		}
		return data[mid];
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		while(scanner.hasNext()) {
			int num = scanner.nextInt();
			int[] data = new int[num];
			
			for(int i=0; i<num; i++) {
				data[i] = scanner.nextInt();
			}
			
			// int min = findMinData(data, 0, data.length - 1);
			int min3 = findMinData3(data);
			
			System.out.println(min3);
		}
	}
}