153. Find Minimum in Rotated Sorted Array

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Code

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        // 使用right和mid作比较可以直到现在在哪一侧
        while(left + 1 < right){
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]){
                left = mid;
            } else if (nums[mid] < nums[right]){
                right = mid;
            }
        }

        if(nums[left] < nums[right]){
            return nums[left];
        } else {
            return nums[right];
        }
    }
}