[数组二分查找] 0153. 寻找旋转排序数组中最小值

1. 题目链接

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

2. 题目大意

描述：给定一个数组 nums，nums 是有升序数组经过「旋转」得到的。但是旋转次数未知。数组中不存在重复元素。

要求：找出数组中的最小元素。

说明：

• 旋转操作：将数组整体右移若干位置。
• n==nums.length。
• 1≤n≤5000。
• −5000≤nums[i]≤5000。
• nums 中的所有整数互不相同。
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转。

3. 示例

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

4. 解题思路

数组经过「旋转」之后，会有两种情况，第一种就是原先的升序序列，另一种是两段升序的序列。

第一种的最小值在最左边。第二种最小值在第二段升序序列的第一个元素。

          *
        *
      *
    *
  *
*

    *
  *
*
          *
        *
      *

最直接的办法就是遍历一遍，找到最小值。但是还可以有更好的方法。考虑用二分查找来降低算法的时间复杂度。

创建两个指针 left、right，指向数组首尾。让后计算出两个指针中间值 mid。将 mid 与两个指针做比较。

1. nums[mid]>nums[right]，最小值不可能在 mid 左侧，一定在 mid 右侧，则将 left 移动到 mid+1 位置，继续查找右侧区间。
2. nums[mid]≤nums[right]，最小值一定在 mid 左侧，或者 mid 位置，将 right 移动到 mid 位置上，继续查找左侧区间。

5. 参考代码

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1; // 闭区间 [0, n-1]
        while (left < right) { // 闭区间不为空
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid; // 保持右边界在闭区间内
            } else {
                left = mid + 1; // 缩小左边界，保持闭区间
            }
        }
        return nums[left];
    }
}