本文共 1660 字，大约阅读时间需要 5 分钟。

问题描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例 1：

输入：nums = [3,4,5,1,2]输出：1

示例 2：

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

示例 3：

输入：nums = [1]输出：1

提示：

1 <= nums.length <= 5000-5000 <= nums[i] <= 5000nums 中的所有整数都是 唯一 的nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转

解题思路

在二分搜索中，我们找到区间的中间点并根据某些条件决定去区间左半部分还是右半部分搜索。

由于给定的数组是有序的，我们就可以使用二分搜索。然而，数组被旋转了，所以简单的使用二分搜索并不可行。

在这个问题中，我们使用一种改进的二分搜索，判断条件与标准的二分搜索有些不同。

我们希望找到旋转排序数组的最小值，如果数组没有被旋转呢？如何检验这一点呢？

如果数组没有被旋转，是升序排列，就满足 last element > first element。

2 3 4 5 6 7

上面例子中 7>2 。说明数组仍然是有序的，没有被旋转。

4 5 6 7 2 3

上面的例子中 3 < 4，因此数组旋转过了。这是因为原先的数组为 [2, 3, 4, 5, 6, 7]，通过旋转较小的

[2, 3] 移到了后面，也就是 [4, 5, 6, 7, 2, 3]。因此旋转数组中第一个元素 [4] 变得比最后一个元素大。

这意味着在数组中你会发现一个变化的点，这个点会帮助我们解决这个问题，我们称其为变化点。

在这个改进版本的二分搜索算法中，我们需要找到这个点。下面是关于变化点的特点：

所有变化点左侧元素 > 数组第一个元素

所有变化点右侧元素 < 数组第一个元素

算法

找到数组的中间元素 mid。

如果中间元素 > 数组第一个元素，我们需要在 mid 右边搜索变化点。

如果中间元素 < 数组第一个元素，我们需要在 mid 左边搜索变化点。

当我们找到变化点时停止搜索，当以下条件满足任意一个即可：

nums[mid] > nums[mid + 1]，因此 mid+1 是最小值。nums[mid - 1] > nums[mid]，因此 mid 是最小值。

实现代码

class Solution {       public int findMin(int[] nums) {           int n=nums.length;        //如果数组中只有一个元素，就直接返回即可        if(n==1){               return nums[0];        }        //如果最后一个元素直接大于第一个元素，就直接返回即可        if(nums[n-1]>nums[0]){               return nums[0];        }        int left=0,right=n-1;        int mid;        while(left<=right){               mid=(left+right)>>1;            if(mid>0 && nums[mid]
   
    nums[mid+1]){                   return nums[mid+1];            }            if(nums[mid]>nums[0]){                   left=mid+1;            }else{                   right=mid-1;            }        }        return -1;    }}