C語言：LeetCode 153尋找旋轉(zhuǎn)排序數(shù)組中的最小值

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。

（ 例如，數(shù)組 ［0，1，2，4，5，6，7］ 可能變?yōu)?［4，5，6，7，0，1，2］ ）。

請(qǐng)找出其中最小的元素。

你可以假設(shè)數(shù)組中不存在重復(fù)元素。

示例 1：

輸入： ［3，4，5，1，2］

輸出： 1

示例 2：

輸入： ［4，5，6，7，0，1，2］

輸出： 0

這道尋找最小值的題目可以用二分查找法來解決，時(shí)間復(fù)雜度為O（logN），空間復(fù)雜度為O（1）。

看一下代碼：

首先說一下主要思路：

單調(diào)遞增的序列：

*

*
*

*

*

做了旋轉(zhuǎn)：

*

*

*

*

*

用二分法查找，需要始終將目標(biāo)值（這里是最小值）套住，并不斷收縮左邊界或右邊界。

左、中、右三個(gè)位置的值相比較，有以下幾種情況：

左值 《 中值， 中值 《 右值 ：沒有旋轉(zhuǎn)，最小值在最左邊，可以收縮右邊界

右

中

左

左值 》 中值， 中值 《 右值 ：有旋轉(zhuǎn)，最小值在左半邊，可以收縮右邊界

左

右

中

左值 《 中值， 中值 》 右值 ：有旋轉(zhuǎn)，最小值在右半邊，可以收縮左邊界

中

左

右

左值 》 中值， 中值 》 右值 ：?jiǎn)握{(diào)遞減，不可能出現(xiàn)

左

中

右

分析前面三種可能的情況，會(huì)發(fā)現(xiàn)情況1、2是一類，情況3是另一類。

如果中值 《 右值，則最小值在左半邊，可以收縮右邊界。

如果中值 》 右值，則最小值在右半邊，可以收縮左邊界。

通過比較中值與右值，可以確定最小值的位置范圍，從而決定邊界收縮的方向。

而情況1與情況3都是左值 《 中值，但是最小值位置范圍卻不同，這說明，如果只比較左值與中值，不能確定最小值的位置范圍。

所以我們需要通過比較中值與右值來確定最小值的位置范圍，進(jìn)而確定邊界收縮的方向。

接著分析解法里的一些問題：

首先是while循環(huán)里的細(xì)節(jié)問題。

這里的循環(huán)不變式是left 《 right， 并且要保證左閉右開區(qū)間里面始終套住最小值。

中間位置的計(jì)算：mid = left + （right - left） / 2

這里整數(shù)除法是向下取整的地板除，mid更靠近left，

再結(jié)合while循環(huán)的條件left 《 right，

可以知道left 《= mid，mid 《 right，

即在while循環(huán)內(nèi)，mid始終小于right。

因此在while循環(huán)內(nèi)，nums［mid］要么大于要么小于nums［right］，不會(huì)等于。

這樣else {right = mid;}這句判斷可以改為更精確的

else if （nums［mid］ 《 nums［right］） {right = mid;}。

再分析一下while循環(huán)退出的條件。

如果輸入數(shù)組只有一個(gè)數(shù)，左右邊界位置重合，left == right，不會(huì)進(jìn)入while循環(huán)，直接輸出。

如果輸入數(shù)組多于一個(gè)數(shù)，循環(huán)到最后，會(huì)只剩兩個(gè)數(shù)，nums［left］ == nums［mid］，以及nums［right］，這里的位置left == mid == right - 1。

如果nums［left］ == nums［mid］ 》 nums［right］，則左邊大、右邊小，

需要執(zhí)行l(wèi)eft = mid + 1，使得left == right，左右邊界位置重合，循環(huán)結(jié)束，nums［left］與nums［right］都保存了最小值。

如果nums［left］ == nums［mid］ 《 nums［right］，則左邊小、右邊大，

會(huì)執(zhí)行right = mid，使得left == right，左右邊界位置重合，循環(huán)結(jié)束，nums［left］、nums［mid］、nums［right］都保存了最小值。

細(xì)化了的代碼：

再討論一個(gè)問題：

為什么左右不對(duì)稱？為什么比較mid與right而不比較mid與left？能不能通過比較mid與left來解決問題？

左右不對(duì)稱的原因是：

這是循環(huán)前升序排列的數(shù)，左邊的數(shù)小，右邊的數(shù)大，而且我們要找的是最小值，肯定是偏向左找，所以左右不對(duì)稱了。

為什么比較mid與right而不比較mid與left？

具體原因前面已經(jīng)分析過了，簡(jiǎn)單講就是因?yàn)槲覀冋易钚≈?，要偏向左找，目?biāo)值右邊的情況會(huì)比較簡(jiǎn)單，容易區(qū)分，所以比較mid與right而不比較mid與left。

那么能不能通過比較mid與left來解決問題？

能，轉(zhuǎn)換思路，不直接找最小值，而是先找最大值，最大值偏右，可以通過比較mid與left來找到最大值，最大值向右移動(dòng)一位就是最小值了（需要考慮最大值在最右邊的情況，右移一位后對(duì)數(shù)組長(zhǎng)度取余）。

以下是先找最大值的代碼，可以與前面找最小值的比較：

使用left 《 right作while循環(huán)條件可以很方便推廣到數(shù)組中有重復(fù)元素的情況，即154題：

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

只需要在nums［mid］ == nums［right］時(shí)挪動(dòng)右邊界就行：

初始條件是左閉右閉區(qū)間，right = nums.size（） - 1，

那么能否將while循環(huán)的條件也選為左閉右閉區(qū)間left 《= right？

可以的，代碼如下：