題目描述

把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回0。

代碼實(shí)現(xiàn)

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array == null)
            return 0;
        int low = 0,high = array.length - 1;
        
        while(low < high){
            int mid = (low + high)/2;
            if(array[mid] > array[high])
                //向右查找
                low = mid + 1;
            else
                //向左查找
                high = mid;
        }
        return array[low];
    }
}

主要思路

1、考查二分查找的使用
2、向右查找的條件，應(yīng)該是array[mid] > array[high]，而不是array[mid] > array[low]，以免出現(xiàn)3,3,3,1,2這種特例
3、嚴(yán)格來說這道題還要考慮3,3,3,1,3這種特例，此時(shí)只能順序查找，可能因?yàn)椴皇强疾橹攸c(diǎn)，此時(shí)測(cè)試用例已全部通過