剑指Offer #06 旋转数组的最小数字（二分查找）| 图文详解

小灰灰 2023-07-08 08:00 18阅读 0赞

> 题目来源：牛客网-剑指Offer专题  
> 题目地址：[旋转数组的最小数字][Link 1]

### 题目描述 ###

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

### 题目解析 ###

**方法一：**  
最直观的方法莫过于**漠视题目给的条件“非递减排序”，直接遍历整个数组找到里面最小的元素**。就算我很菜，也不忍下手写这样的代码。

于是，对暴力法稍加优化才有了第一种算法：**以第一个元素  a r r a y \[ 0 \] array\[0\] array\[0\] 为基准找到第一个比它小的元素，这个就是原数组的第一个元素，即最小值**。找不到则返回第一个元素，说明没有元素参与旋转。![1][]  
虽然做了优化，在极端情况下还是要遍历整个数组，时间复杂度  O ( n ) O(n) O(n)。

import java.util.ArrayList;
    public class Solution { 
        public int minNumberInRotateArray(int [] array) { 
        	//特判
            if (array.length == 0) { 
                return 0;
            }
            //以第一个元素为基准
            int flag = array[0];
            for (int i = 1; i < array.length; i++) { 
            	//找到第一个比它小的元素，即为答案
                if (flag > array[i]) { 
                    return array[i];
                }
            }
            return flag;
        }
    }

**方法二：**  
通常在有序的序列中查找某个值的问题都可以用二分查找，本题虽然不是整个序列又是有序的，但是它也算是局部有序，也可以用上二分查找。

经过观察我们可以发现，旋转数组可以分成左右两个部分，而我们**要找的数就在分界线的右边**。算法描述如下：

*  首先，我们设定左右指针  l e f t left left 和  r i g h t right right ，然后通过判断中间指针  m i d mid mid 指向的数是否比  r i g h t right right 指向的数小。
 *  如果是，则说明  m i d mid mid 位于数组右边部分，于是将  r i g h t right right 指针移动到该位置上；否则，说明  m i d mid mid 位于数组左边部分，于是将指针移动到该位置上。
 *  最后不断重复上诉过程，直到找到数组两个部分的边界所在，即  r i g h t − l e f t = 1 right-left=1 right−left=1。这时， a r r a y \[ r i g h t \] array\[right\] array\[right\] 就是我们要找的最小值。  
    ![2][]

二分查找的过程如上图所示 ，算法时间复杂度为  O ( l o g n ) O(logn) O(logn)。

import java.util.ArrayList;
    public class Solution { 
        public int minNumberInRotateArray(int [] array) { 
            if (array.length == 0) { 
                return 0;
            }
            int left = 0, right = array.length - 1;
            while (array[left] >= array[right]) { 
                int mid = (left + right) / 2;
                //找到边界所在
                if (right - left == 1) break;
                if (array[mid] < array[right]) { 
                    right= mid;
                } else { 
                    left= mid;
                }
            }
            return array[right];
        }
    }

虽然这样在牛客网中通过了，但是我发现了一组可以hack这份代码的数据：  
 \[ 3 , 4 , 1 , 3 , 3 , 3 , 3 \] \[3,4,1,3,3,3,3\] \[3,4,1,3,3,3,3\]  
正确答案：  1 1 1  
代码返回：  3 3 3

**方法三：**  
有问题就肯定会有对策，这里借用牛客网大佬[FINACK][]的思路。

分下面三种情况进行讨论：

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

注意这里有个坑：**如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字**，比如 array = \[4,6\]，此时array\[left\] = 4 ；array\[mid\] = 4；array\[right\] = 6；如果right = mid - 1，就会产生错误， 因此right = mid。

import java.util.ArrayList;
    public class Solution { 
        public int minNumberInRotateArray(int [] array) { 
            if (array.length == 0) { 
                return 0;
            }
            int left = 0, right = array.length - 1;
            while (left < right) { 
                int mid = (left + right) / 2;
                if (array[mid] > array[right]) { 
                    left = mid + 1;
                } else if (array[mid] == array[right]) { 
                    right--;
                } else { 
                    right = mid;
                }
            }
            return array[left];
        }
    }

只是可惜，在所有数字都一样的情况下，算法的时间复杂度会退化成  O ( n ) O(n) O(n)。当然，这是没有办法的事情。

--------------------

如果本文对你有所帮助，要记得点赞哦~

[Link 1]: https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[1]: https://img-blog.csdnimg.cn/2020022523211364.png
[2]: https://img-blog.csdnimg.cn/20200226001204565.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[FINACK]: https://www.nowcoder.com/profile/519819