题解 | #旋转排列之找出最矮的牛#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param heights int整型一维数组
     * @return int整型
     */
    public static int findMin (int[] heights) {
        // write code here
        int start = 0;
        int end = heights.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (mid==0 && heights[mid]<heights[mid+1]) {
                return heights[0];
            } else if (mid == heights.length-1 && (heights[mid]<heights[mid-1])){
                if(heights[mid]<heights[0]) {
                    return heights[heights.length-1];
                }else{
                    return heights[0];
                }
            } else if(heights[mid]<heights[mid-1] && heights[mid]<heights[mid+1]){
                return heights[mid];
            } else if(heights[mid-1]>heights[mid] && heights[mid]>heights[mid+1]){
                start = mid+1;
            } else if(heights[mid]>heights[mid+1] && heights[mid]>heights[mid-1]){
                end = mid-1;
            }
        }
        return heights[start];
    }

}

本题主要考察的是双指针，所用编程语言是java.解题步骤如下：

定义两个变量 left 和 right，分别表示数组的左边界和右边界，初始值为 0 和 n-1，其中 n 是数组的长度。

计算中间位置 mid = (left + right) / 2，向下取整。

比较数组中的 mid 位置的元素和其余位置元素的关系

如果mid位置是数组最后一个位置，mid比前面一个位置元素小，如果比第一个元素小，则此位置元素最小，否则就是第一个位置。

如果mid位置是数组第一个位置，mid比后面一个位置元素小，则此位置元素最小。

如果mid位置是中间位置，如果mid位置比前面位置和后面位置元素都小，则此位置元素最小；

如果mid位置比前面位置元素小，比后面位置元素大 start=mid+1

如果mid位置比前面位置元素大，比后面位置元素大 end=mid-1