学步园

【题目描述】

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4
5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

【算法思路】利用折半查找(或者二分查找)的思路去查找这个最小元素

【编程步骤】

 * 1. 如果数组num只有一个元素，则所求的最小的元素就是它了；
 * 2. 若left到right位置的元素严格递增，则最小的元素为num[left]，如左图

否则，如右图，利用折半查找，若left到mid递增有序，则最小元素必出现在右边部分：mid+1到right；

若mid到right递增有序，则最小元素出现在左边部分：left到mid；

while(left<right){
            if(num[left]<num[right]){
                return num[left];
            }else{
                int mid=(left+right)/2;
                if(num[mid]>=num[left])
                    left=mid+1;
                else if(num[mid]<num[right])
                    right=mid;
            }
        }

 * 3. 返回最小元素num[left]

【代码实现】

public class Solution {
    public int findMin(int[] num) {
        if(num.length==1)   
            return num[0];
        int left=0;
        int right=num.length-1;
        while(left<right){
            if(num[left]<num[right]){
                return num[left];
            }else{
                int mid=(left+right)/2;
                if(num[mid]>=num[left])
                    left=mid+1;
                else if(num[mid]<num[right])
                    right=mid;
            }
        }
        return num[left];
        
    }
}

【复杂度分析】

时间上：每次折半查找排除左半边或右半边递增有序的部分，为O(log n)

空间上：O(1)