力扣面试150题--寻找旋转排序数组中的最小值

Day 86

题目描述

思路

我们考虑一下如果选择数组会出现的情况：

1. 旋转n次，等于没转，那么第一个元素就是最小的
2. 旋转1-n-1次，那么第一个元素肯定是大于最后一个元素的（这个很重要）
   我们基于以上的思路，那么判断一个数组是否旋转的条件就很明确了，比较第一个元素和最后一个元素的大小。
   好，这里如果没转直接返回第一个元素就好。
   那么发生旋转了，我们就考虑如何二分查找
   二分查找的先决条件是有序，那么哪里有序呢？此时数组是由两段有序数列组成的，第一段肯定不存在我们要的最小值，第二段有序的数组的第一个元素就是最小值

那么我们就开始二分查找，此时数组是由两段有序数列组成的，前一段我们肯定找不到最小的值，我们的mid如果在这个区间（比较num[mid]和最后一元素的值），我们就得让他向前走，所以beg=mid+1，让他快速的进入第二段有序数列中去。

此时我们到了第二段有序的数列，但可能mid和beg是处于第二段有序数列的中间，我们判断这个mid是否是周围的最小值，如果不是，那么我们需要beg和mid向前移动，于是beg–，end=mid
此时由于我们要比较mid左右的值，防止越界 特判一下第一个元素和最后一个元素

class Solution {public int findMin(int[] nums) {int beg=0;int end=nums.length-1;int min=nums[nums.length-1];if(nums[nums.length-1]>=nums[0]){return nums[0];//说明没有旋转}while(beg<=end){int mid=beg+(end-beg)/2;if(nums[mid]>min){//目的是找最后的那个有序数列beg=mid+1;}else{if(mid==nums.length-1||mid==0){return Math.min(nums[0],nums[nums.length-1]);}if(nums[mid]<nums[mid-1]&&nums[mid]<nums[mid+1]){return nums[mid];}else{beg--;end=mid;}}}return min;}
}