JZ6:把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

系统管理员 2022-11-26 07:42 49阅读 0赞

## 题目描述 ##

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

## 过程： ##

非递减序列 **前一个数![\\leqslant][leqslant]后一个数 ，**于是旋转只有前一个数＞后一个数时候，后一个数就是最小值。

import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array){ 
            if(array.length==0){
                return 0;
            }
            for(int i=0;i<array.length-1;i++){
                if((array[i]>array[i+1])){
                    return array[i+1];
                }
            }
            return array[0];
        }
    }

再去看看题解里有什么大宝贝。

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

## 二分查找啊 ##

看到这种题目，正确做法基本上都是需要使用**二分查找**。

对于这种**变形的二分查找**的考察，**解决思路**主要都是：观察 left、mid、right 三个指针对应的元素的大小关系，然后移动指针。

具体的**解决方法**主要是：多写几个例子，然后观察如何移动。

举几个例子来推导解题细节（请记住题干的数组有序、某个点旋转这两个条件）：

*   `arr[left] < arr[right]`: 直接返回`arr[left]`。例如：`1 2 3 4 5`
    
    --------------------
    
    以下情况全都是 `arr[left]  arr[right]`:
 *  如果right-left=1，则右就是结果。
 *  `arr[left] arr[mid]`: 说明从数组下标范围为`[left, right]`的元素是递增的，此时最小值只可能出现在`[mid , length)`范围内。例如:`4 5 1 2 3`
 *  `arr[mid]  arr[right]`: 说明从数组下标范围为`[mid, right]`的元素是递增的，此时最小值只可能出现在`[left, mid]` 范围内。注意，这里不能跳过下标`mid`。例如：`3 3 3 4 5`

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

[leqslant]: https://private.codecogs.com/gif.latex?%5Cleqslant