153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

二分搜索，寻找断裂点。
当left小于right时循环。
每次计算出mid，分为两种情况：

• 如果nums[mid]小于nums[nums.length-1]，则右半侧为顺序的。
• 反之则左半侧为顺序，右半侧为无序的。
  以此来更新搜索范围。
  由于mid计算公式向下取整。
  当更新left时更新为mid+1，向前一格。
  当更新right时更新为mid。
  最后返回nums[left]。

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