leetCode-153:Find Minimum in Rotated Sorted Array

问题描述

给定一个旋转过的升序数组，要求找出数组中的最小元素。题目链接：**点我**

样例输入输出

输入：[3,4,5,1,2]

输出：1

输入：[4,5,6,7,0,1,2]

输出：0

问题解法

此题最直观暴力的一种做法就是顺序遍历找出最小的元素。但是这很明显就无法利用 “升序” 的这一特点。所以遍历数组肯定不是题目的本意。观察旋转的升序数组，可以发现，如果数组第一个数字比最后一个数字大，那就说明数组是旋转过的，可以不断使用二分查找的方式进行排查过滤。如果数组第一个元素比最后一个数字大，那说明数组已经是有序的升序数组了，此时直接返回第一个元素即可。代码如下

class Solution
{
    public int findMin(int[] nums)
    {
        if (nums.length == 1)
        {
            return nums[0];
        }
        
        int start = 0;
        int end = nums.length - 1;
        if (nums[start] < nums[end])
        {
            return nums[start];
        }

        while (start + 1 != end)
        {
            int middle = (start + end) / 2;
            if (nums[start] > nums[middle])
            {
                end = middle;
            }
            else
            {
                start = middle;
            }
        }

        return Math.min(nums[start], nums[end]);
    }
}