1 題目

??尋找旋轉(zhuǎn)排序數(shù)組中的最小值（Find Minimum in Rotated Sorted Array）

lintcode：題號(hào)——159，難度——medium

2 描述

??假設(shè)一個(gè)按升序排好序的數(shù)組在其某一未知點(diǎn)發(fā)生了旋轉(zhuǎn)（比如0 1 2 4 5 6 7 可能變成4 5 6 7 0 1 2）。你需要找到其中最小的元素。（可以假設(shè)數(shù)組中不存在重復(fù)元素。）

??名詞：

RSA：旋轉(zhuǎn)排序數(shù)組，即Rotated Sorted Array

??樣例1：

輸入：[4, 5, 6, 7, 0, 1, 2]
輸出：0
解釋：

數(shù)組中的最小值為0

??樣例2：

輸入：[2,1]
輸出：1
解釋：

數(shù)組中的最小值為1

3 思路

??如果不考慮耗時(shí)，通過從頭遍歷的方式的時(shí)間復(fù)雜度為O(n)。考慮優(yōu)化，RSA是正常的排序數(shù)組通過旋轉(zhuǎn)得到的，以升序數(shù)組為例，旋轉(zhuǎn)后的數(shù)組可以看作前后兩段升序數(shù)組。前半段的所有值都大于后半段的所有值，需要尋找最小值，即后半段的首個(gè)元素，考慮以折半查找的方式，每次縮小一半的目標(biāo)區(qū)間。

1. 找到中點(diǎn)元素；
2. 比較中點(diǎn)元素與末尾元素，根據(jù)情況拋掉最小值不可能存在的區(qū)間；
3. 重復(fù)直到目標(biāo)區(qū)間足夠小，找到最小值。

??在第二步中，選擇數(shù)組的末尾元素為參照對象進(jìn)行比較，如果中點(diǎn)元素大于末尾元素，表明中點(diǎn)元素在前升序區(qū)間內(nèi)，因?yàn)樽钚≈挡豢赡艽嬖谟谇吧騾^(qū)間，所以拋掉前半段，折半目標(biāo)區(qū)間；如果中點(diǎn)元素小于末尾元素，表明中點(diǎn)元素在后升序區(qū)間內(nèi)，因?yàn)樯虻脑颍蛴业乃性囟疾粫?huì)是最小值，所以可以拋掉后半段，同樣能夠折半目標(biāo)區(qū)間。

為什么不用首位元素做為參照對象？

步驟2中以末尾元素為參照對象，如果使用首位元素為參照對象，表面上同樣能夠區(qū)分中點(diǎn)元素的位置并折半目標(biāo)區(qū)間，但是考慮標(biāo)準(zhǔn)的升序數(shù)組（可以看成未旋轉(zhuǎn)，或者旋轉(zhuǎn)了整圈又回到遠(yuǎn)點(diǎn)的RSA），以末尾元素為參照，末尾元素始終大于中點(diǎn)元素，拋掉的一直是后半段，直到找到最小值；以首位元素為參照，首位元素始終小于中點(diǎn)元素，拋掉的是前半段，而最小值也被拋掉了，導(dǎo)致結(jié)果不正確。

技巧

選擇參照對象的時(shí)候，永遠(yuǎn)使用與目標(biāo)值（被尋找的最大、最小值）在同一升序、降序區(qū)間的端點(diǎn)。
即在升序時(shí)尋找最小值，由于最小值在后區(qū)間，我們選擇末尾元素為參照對象；
在升序是尋找最大值，由于最大值在前區(qū)間，我們選擇首位元素為參照對象；
在降序時(shí)尋找最小值，由于最小值在前區(qū)間，我們選擇首位元素為參照對象；
在降序是尋找最大值，由于最大值在后區(qū)間，我們選擇末尾元素為參照對象。

3.1 圖解

3.2 時(shí)間復(fù)雜度

??算法的時(shí)間復(fù)雜度為O(log n)

3.3 空間復(fù)雜度

??算法的空間復(fù)雜度為O(1)

4 源碼

??注意事項(xiàng)：

返回的是最小值，不是序號(hào)。

??C++版本：

/**
* @param nums: 旋轉(zhuǎn)排序數(shù)組（RSA）
* @return: 數(shù)組中的最小值
*/
int findMin(vector<int> &nums) {
    // write your code here
    if (nums.empty())
    {
        return -1;
    }

    int start = 0;
    int end = nums.size() - 1;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (nums.at(mid) > nums.at(end))
        {
            start = mid;
        }
        if (nums.at(mid) < nums.at(end))
        {
            end = mid;
        }
    }

    if (nums.at(start) < nums.at(end))
    {
        return nums.at(start);
    }
    else
    {
        return nums.at(end);
    }
}