153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order 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.

一刷
思路：首先判断序列是不是ascending的。如果不是，然后再判断左half还是右half是ascending的。

public class Solution {
    public int findMin(int[] nums) {
        if(nums.length == 0) return -1;
        int lo = 0, hi = nums.length-1;
        while(lo<hi){
            if(nums[lo]<nums[hi]) return nums[lo];
            int mid = lo + (hi-lo)/2;
            
            if(nums[mid]>=nums[lo]){//left half is sorted
                lo = mid+1;
            }else{
                hi = mid;//should not exclusive the mid
            }
        }
        return nums[lo];
    }
}