假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。

你需要找到其中最小的元素。

数组中可能存在重复的元素。

解题

暴力直接线性查找

或者，线性找到第一个开始降序的位置对应的数

应该考虑二分法

递归 + 二分

public class Solution {    /**     * @param num: a rotated sorted array     * @return: the minimum number in the array     */    public int findMin(int[] num) {        // write your code here        if( num == null || num.length == 0)            return 0;        if(num.length == 1)            return num[0];        return findMin(num,0,num.length - 1);            }    public int findMin(int[] num,int left,int right){        if(left == right)            return num[left];        if(right == left + 1)            return Math.min(num[left],num[right]);        int mid = (left + right)/2;        if( num[right] > num[left])            return num[left];        else if( num[right] == num [left])            return findMin(num,left + 1,right);        else if(num[mid] >= num[left])            return findMin(num,mid,right);        else             return findMin(num,left,mid);    }}

 

二分

public class Solution {    /**     * @param num: a rotated sorted array     * @return: the minimum number in the array     */    public int findMin(int[] num) {        // write your code here        if( num == null || num.length == 0)            return 0;        if(num.length == 1)            return num[0];        int low = 0;        int high = num.length -1;        int mid = low;        while(low < high){            mid = (low + high)/2;            if(num[mid] >  num[high]){                low = mid + 1;            }else if( num[mid] < num[high]){                high = mid ;            }else{                high--;            }        }        return num[low];            } }