題目：尋找旋轉排序數組中的最小值

 假設一個旋轉排序的數組其起始位置是未知的（比如0 1 2 4 5 6 7 可能變成是4 5 6 7 0 1 2）。

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

你可以假設數組中不存在重複的元素。

您在真實的面試中是否遇到過這個題？

Yes

樣例

給出[4,5,6,7,0,1,2]  傳回 0

标簽 Expand   

相關題目 Expand   

解題思路: 1.直接O(n)周遊，選出最小的元素。不做AC代碼 2. 由于是經過排序的數組，利用這個特性可以使用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
         int left = 0;
         int right = num.length-1;
         if(num[left]<num[right]){
              return num[left];
         }
         while(left<right){
              int mid = (left+right)/2;
              if(num[mid]<num[right]){
                   right = mid;
              }else{
                   left = mid+1;
              }
         }
         return num[left];
    }
}