旋转数组的最小值

问题描述

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

思路分析

这里有一个条件，就是观察发现，它是将原本有序的数组划分成两块，左边有序快依次递增并且总是大于右边有序块，所以很自然想到二分查找法，就是利用low，mid，high引用依次比较，mid值到底比左边还是右边大，也就是说不断缩小最小值的查找范围，然而还有一种情况就是low、mid。high三者值相等得情况，例如{1,0,1,1,1}，很显然mid不好确定范围，这属于特殊情况，可以采用顺序查找，找到数组中较小者，然后返回

码上有戏

public class Findmin {

	public int min(int[] arr){
		if(arr==null||arr.length-1<0)
			return 0;
		 int low=0;
		  int high=arr.length-1;
		    int mid=low;
		      while(arr[low]>=arr[high]){
		    	  mid=(low+high)/2;
		    	   if(high-low==1){
		    		   return arr[high];
		    	   }
		    	   if(arr[low]==arr[mid]&&arr[mid]==arr[high])
		    	   {
		    		   return search(arr,low,high);
		    	   }
		    	   if(arr[mid]>arr[low])
		    		   low=mid;
		    	   else if(arr[mid]<arr[high])
		    		   high=mid; 		   
		      }
		      return arr[mid];
	}
	
	
	private int search(int[] arr, int low, int high) {
		int result=arr[high];
		for(int i=low+1;i<=high;i++)
			if(result>arr[i])
			{
				result=arr[i];
			}
		return result;
	}


	public static void main(String[] args) {
		int minNumber=new Findmin().min(new int[]{1,0,1,1,1});
		System.out.println(minNumber);

	}

}