LeetCode 153. Find Minimum in Rotated Sorted Array（二分）

Find Minimum in Rotated Sorted Array

Medium

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

题意

给定一个旋转的升序数组nums，即数组从一个随机位置开始是旋转升序的，求数组的最小值

思路

二分查找。把当前位置的值和数组头比较，如果nums[mid] < nums[0]则在mid的左边继续查找，如果nums[mid] > nums[0]则在mid的右边继续查找。

注意两个特殊情况：

1. mid = 0，说明数组头是最大值，相应地数组最小值就是数组头的后面一个元素
2. 数组头本身就是数组最小值

代码

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