旋转数组的最小数字

Question

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1。
NOTE：给出的所有元素都大于 0，若数组大小为 0，请返回 0。

地址

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

①最简单的思想就是一趟循环遍历找到最小值。但时间复杂度为 O(n)。

进一步发现，由于原序列基本有序，因此最大值后面那个就是最小值。

②分治--二分查找 O(logn)

和二分查找法一样，用两个指针分别指向数组的第一个元素和最后一个元素。

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还可以注意到最小的元素刚好是这两个子数组的分界线。

我们试着用二元查找法的思路在寻找这个最小的元素。使用二分查找加快查找的速度，每次都能缩小查找的范围。

二分查找时间复杂度：（无非就是while循环的次数！）
因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
一次二分剩下的元素：n/2
两次二分剩下的元素：n/2/2 = n/4
…
m次二分剩下的元素：n/(2^m)
在最坏情况下是在排除到只剩下最后一个元素之后得到结果，即
n/(2^m)=1
所以由上式可得 ： 2^m=n
进而可求出时间复杂度为： log2(n)

思路：
1、我们用两个指针low和high分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于等于最后一个元素的；但是如果不是旋转，第一个元素肯定小于或等于最后一个元素。
2、找到数组的中间元素。中间元素大于最后一个元素，则中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针low指向中间元素。
3、中间元素小于最后一个元素，则中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针high指向中间元素。
4、中间元素等于最后一个元素，则将第二个指针向前移，然后继续比较。

总之，需要考虑三种情况：

• array[mid] > array[high]: 出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
  low = mid + 1;
• array[mid] == array[high]: 出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边 还是右边,这时只好一个一个试
  high = high - 1
• array[mid] < array[high]: 出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左边。因为右边必然都是递增的。
  high = mid

function F(arr) {
    if(!arr || arr.legnth === 0) {
        return;
    }

    let low = 0;
    let high = arr.length - 1;
    let mid;

    if(arr[low] < arr[high]) {
        return arr[low]; // 如果第一个元素小于最后一个元素 则该数组将整个数组移到数组结尾相当于原数组
    }

    while(low < high) {
        mid = Math.floor((low + high) / 2);
        if(arr[mid] < arr[high]) {
            high = mid;
        } else if(arr[mid] > arr[high]) {
            low = mid + 1;
        } else {
            high = high - 1;
        }
    }
    return arr[low];
}

单元测试

1、典型输入，单调升序的数组的一个旋转[3, 4, 5, 1, 2]
2、有重复数字，并且重复的数字刚好的最小的数字[3, 4, 5, 1, 1, 2]
3、有重复数字，但重复的数字不是第一个数字和最后一个数字 [3, 4, 5, 1, 2, 2]
4、有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字[1, 0, 1, 1, 1]
5、单调升序数组，旋转0个元素，也就是单调升序数组本身[1, 2, 3, 4, 5]
6、数组中只有一个数字
7、鲁棒性测试：输入NULL

参考文献

旋转数组的最小数字