1. 题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为 1。

2. 解题思路

最简单的肯定是从头到尾遍历,复杂度是 $O(N)$。这种方法没有利用“旋转数组”的特性

借助二分查找的思想,时间复杂度可以降低到 $O(log(N))$。

可以通过以下方法确定最小值元素的位置,然后移动指针,缩小范围:

  • 中间指针对应的元素 ≥ 左侧元素, 那么中间元素位于原递增数组中, 最小值在右侧
  • 中间指针对应的元素 ≤ 右侧元素, 那么中间元素位于被移动的递增数组中,最小值在左侧

特殊情况,如果三者相等,那么无法判断最小值元素的位置,就退化为普通遍历即可。

3. 代码

先上一段二分查找和实现思路:

/**
 * 二分查找
 * @param {Array} arr
 * @param {*} elem
 */
function binarySearch(arr, elem) {
  let left = 0,
    right = arr.length - 1,
    mid = -1;

  while (left <= right) {
    // 注意是≤:考虑只剩1个元素的情况
    mid = Math.floor((left + right) / 2);

    if (arr[mid] === elem) {
      return true;
    }

    if (elem < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return false;
}

/**
 * 测试代码
 */
console.log(binarySearch([1, 2], 2));
console.log(binarySearch([1, 2], -1));
console.log(binarySearch([1, 2, 10], 2));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

借助二分查找的思想,写出本题代码:

/**
 * 在arr[left, right]中顺序查找最小值
 * @param {Array} arr
 * @param {Number} left
 * @param {Number} right
 */
function orderSearchMin(arr, left, right) {
  let min = arr[left];

  for (let i = left + 1; i <= right; ++i) {
    arr[i] < min && (min = arr[i]);
  }

  return min;
}

/**
 * 在旋转数组arr中用二分法查找最小值
 * @param {Array} arr
 */

function binSearchMin(arr) {
  if (!Array.isArray(arr) || !arr.length) {
    throw Error("Empty Array");
  }

  let left = 0,
    right = arr.length - 1,
    mid = null;

  while (left < right) {
    if (right === 1 + left) {
      return arr[right];
    }

    mid = Math.floor((left + right) / 2);

    if (arr[mid] === arr[left] && arr[mid] === arr[right]) {
      // 无法判断最小值位置
      return orderSearchMin(arr, left, right);
    }

    if (arr[mid] >= arr[left]) {
      // 最小值在右边
      left = mid;
    } else if (arr[mid] <= arr[right]) {
      // 最小值在左边
      right = mid;
    }
  }

  return arr[right];
}

/**
 * 测试代码
 */

console.log(binSearchMin([3, 4, 5, 1, 2]));
console.log(binSearchMin([2, 3, 4, 5, 1]));
console.log(binSearchMin([2, 2, 2, 1, 1, 2]));
console.log(binSearchMin([1]));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62