153.find-minimum-in-rotated-sorted-array.java

/*
 * @lc app=leetcode id=153 lang=java
 *
 * [153] Find Minimum in Rotated Sorted Array
 *
 * https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
 *
 * algorithms
 * Medium (44.34%)
 * Likes:    1826
 * Dislikes: 217
 * Total Accepted:    406.8K
 * Total Submissions: 914.9K
 * Testcase Example:  '[3,4,5,1,2]'
 *
 * 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.
 * 
 * Example 1:
 * 
 * 
 * Input: [3,4,5,1,2] 
 * Output: 1
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: [4,5,6,7,0,1,2]
 * Output: 0
 * 
 * 
 */

// @lc code=start

// 153. Find Minimum in Rotated Sorted Array

// if nums[mid] > nums[h], right is in order

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

// @lc code=end