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

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.解题步骤如下：

1. 定义两个变量 left 和 right，分别表示数组的左边界和右边界，初始值为 0 和 n-1，其中 n 是数组的长度。
2. 计算中间位置 mid = (left + right) / 2，向下取整。
3. 比较数组中的 mid 位置的元素和其余位置元素的关系

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

1. 如果相等，说明找到了 target 的一个位置，然后向左右两边扩展，找到 target 的起始位置和结束位置，返回 [start, end]。如果小于 target，说明 target 在 mid 的右边，更新 left = mid + 1。如果大于 target，说明 target 在 mid 的左边，更新 right = mid - 1。
2. 重复步骤 2 和 3，直到 left > right，说明没有找到 target，返回 [-1, -1]。