旋转排序数组中的最小值II

发表于
本文字数： 896 阅读时长 ≈ 1 分钟

LeetCode每日一题，154. 寻找旋转排序数组中的最小值II

先看题目描述

cNrPte.png

算法和思路

二分查找

这题使用二分查找即可，虽然说二分查找只可以用于有序数组，但这题的数组是有序数组经旋转形成的，仅有局部的有序性，还是可以利用该数组的性质使用二分查找

在二分查找的每一步中，l 为左边界， r 为右边界，mid 为查找区间的中点，最小值在该区间内

我们每次比较 nums[mid] 与 nums[r] 的大小：

  • 若 nums[mid] < nums[r]，则说明最小值在左半部分中，可以忽略右半部分，令 r = mid
  • 若 nums[mid] > nums[r]，则说明最小值在右半部分中，可以忽略左半部分，令 l = mid + 1
  • 否则，此时无法判断最小值在左半部分还是右半部分中，仅知道 nums[mid] 与 nums[r] 相等，缩小区间，令 r - 1

最后查找结束时返回 nums[l] 即可

算法源码

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else if (nums[mid] > nums[r]){
                l = mid + 1;
            } else {
                r--;
            }
        }
        return nums[l];
    }
}