题目：寻找旋转排序数组中的最小值

 假设一个旋转排序的数组其起始位置是未知的（比如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];
    }
}