旋转数组的最小数

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

LeetCode每日一题，剑指 Offer 11. 旋转数组的最小数字

先看题目描述

算法和思路

循环二分法

  • 初始化三个指针 low = 0，high = numbers.length - 1，mid = （low + high) / 2
  • 开始循环二分
    • 若 numbers[mid] > numbers[high]，说明最小值在 mid 右边，即 [mid + 1, high] 区间，令 low = mid + 1
    • 若 numbers[mid] < numbers[high]，说明最小值在 mid 左边，即 [low, mid] 区间，令 high = mid
    • 若 numbers[mid] = numbers[high]，则无法判断最小值在 mid 左边还是右边，则令 high = high - 1 缩小搜索范围
  • 当 low >= high 时，退出循环二分，返回 numbers[low]

算法源码

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