154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II - 力扣（LeetCode）

已知一個長度為?n?的數(shù)組，預(yù)先按照升序排列，經(jīng)由?1?到?n?次?旋轉(zhuǎn)?后，得到輸入數(shù)組。例如，原數(shù)組?nums = [0,1,4,4,5,6,7]?在變化后可能得到：

• 若旋轉(zhuǎn)?4?次，則可以得到?[4,5,6,7,0,1,4]
• 若旋轉(zhuǎn)?7?次，則可以得到?[0,1,4,4,5,6,7]

注意，數(shù)組?[a[0], a[1], a[2], ..., a[n-1]]?旋轉(zhuǎn)一次?的結(jié)果為數(shù)組?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

給你一個可能存在?重復(fù)?元素值的數(shù)組?nums?，它原來是一個升序排列的數(shù)組，并按上述情形進行了多次旋轉(zhuǎn)。請你找出并返回數(shù)組中的?最小元素?。

你必須盡可能減少整個過程的操作步驟。

示例 1：

輸入：nums = [1,3,5]
輸出：1

示例 2：

輸入：nums = [2,2,2,0,1]
輸出：0

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums?原來是一個升序排序的數(shù)組，并進行了?1?至?n?次旋轉(zhuǎn)

class Solution {public int findMin(int[] nums) {//暴力解題// int len = nums.length;// int ans = nums[0];// for(int i = 1 ;i < len ; i++) {//     if(nums[i] < ans) {//         ans = nums[i];//     }// }// return ans;int left = 0;int right = nums.length - 1;while(left < right) {int mid = (left+right) / 2;if(nums[mid] < nums[right]) right = mid;else if(nums[mid] > nums[right]) left = mid+1;else right--;}return nums[left];}
}

? ? ? ? 每日一題，今天是困難題。這道題目考察的二分很有意思。

? ? ? ? 讀完題目，發(fā)現(xiàn)這道題就是讓我們?nèi)ふ易钚≈?。那最暴力的方法也就是O（n）的方法，直接循環(huán)一次數(shù)組就可以得到最小值了。

? ? ? ? 二分的方法怎么做呢？題目這里是會旋轉(zhuǎn)數(shù)組的，也就是說，不知道數(shù)組會怎么樣被選擇，但，不論怎么旋轉(zhuǎn)其實都可以知道有一個斷點（當然，前后必須是連起來的，也就是0下標的前面對應(yīng)的是nums.length-1下標的數(shù)）。這里用left，right來記錄左右邊界。由于一開始是升序的數(shù)組，那么一定可以知道right下標對應(yīng)的數(shù)是斷點之后最大的數(shù)。我們分情況來看。

????????1.有旋轉(zhuǎn)，且旋轉(zhuǎn)沒有剛好復(fù)原

????????這種情況下，斷點一定在數(shù)組中間，至少不會在邊界0和 len-1的地方，那么這時候lerft所指向的數(shù)一定是大于等于right的，因為原數(shù)組是遞增的。這時候的中點由于在中間，有3種情況：

? ? ? ? （1）如果nums[mid]>nums[right]說明，mid所在的位置，一定在斷點之前。因為nums[left]都大于等于nums[right]了，nums[mid]又大于nums[right]，所以這時候說明mid左邊都還是遞增的。由于大于nums[right]，說明mid的左邊不可能有比right小的，所以left = mid+1。

? ? ? ? （2）如果nums[mid]<nums[right]說明，mid所在的位置，由于小于nums[right]，一定在斷點之后。因為nums[right]是斷點之后最大的，而nums[left]又大于等于right，所以說明此時mid的右邊是都是遞增的，還沒有到達斷點。right = mid。

? ? ? ? （3）如果nums[mid] == nums[right]有可能自mid之后都是nums[right]的值，也就是一條直線，這時候要往后退一個位置。因為即使退一個位置，right的值也不會變，而mid的值卻可以往后退1位，就可以再進行判斷。如果這時候直接讓right=mid，有可能錯過斷點的位置。

? ? ? ?2.順序

? ? ? ? 順序的話其實right就是最大的，會一直往左邊退，直到退到0的位置。

? ? ? ? 3.逆序

? ? ? ? 逆序?qū)嶋H上right是最小的，會一直往右邊進，直到right的位置。

????????這道題目對二分的理解很有幫助。

?