题解 | #旋转数组的最小数字#
旋转数组的最小数字
http://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
原来是递增数列,旋转后分成两个递增数列,并且前一个数列的首位大于后一个数列的末尾 123456->456123 找到两个递增的截断位
1.首先判断首位是否大于末位 大于的话说明进行了旋转 不大于的话就可以直接输出首位
2.mid赋值 判断mid位的数和low/high之间的关系
3.mid位如果大于low位,low到mid是递增的,low就移到mid后一位
4.mid位如果小于high位,mid到high递增,high移到mid
5.如果都不满足,low就直接后移
6.重复判断过程
import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int len=array.length; int low=0; int high=len-1; int mid=0; while(low<high){ if(array[low]<array[high]){ return array[low]; } mid=low+(high-low)/2; if(array[mid]>array[low]){ low=mid+1; } else if(array[mid]<array[high]){ high=mid; } else low++; } return array[low]; } }