LeetCode 153. Find Minimum in Rotated Sorted Array

Problem

LeetCode 153. Find Minimum in Rotated Sorted Array

1. 题目简述

有一个单调递增的数组，它从中间某个地方被rotate了，找到数组中的最小数字，保证所有数字不重复。例如：

• [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.

  Example：
  Input: nums = [3,4,5,1,2]
  Output: 1
  Explanation: The original array was [1,2,3,4,5] rotated 3 times.

2. 算法思路

Binary Search

这道题目也属于二分搜索的经典题目，与之一起的还有LeetCode 154. Find Minimum in Rotated Sorted Array II。

其实这里就是普通的二分法查找，但是难点是在于check的条件，究竟是大于还是大于等于！！！

3. 解法

class Solution {
    public int findMin(int[] nums) {
        if (nums[nums.length - 1] >= nums[0]) {
            return nums[0];
        }
        
        int split = nums[0], l = 0, r = nums.length - 1;
        
        while(l < r) {
            int mid = l + r >> 1;
            // 这里需要注意的点在于是大于还是大于等于，乍一看数字是unique的，但是实际上，有等于的可能性。比如[2,1]这个反例，nums[mid] == split。这里要注意。
            if (nums[mid] >= split) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        
        return nums[l];
    }
}