旋轉數(shù)組的最小數(shù)字

題目

給定一個遞增的旋轉數(shù)組A，返回旋轉數(shù)組中的最小值。旋轉數(shù)組：給定一個已排序的數(shù)組，假設為升序，想象數(shù)組是一個環(huán)形數(shù)組，向左或向右撥動數(shù)組，即可形成旋轉數(shù)組。

解析

如果采用遍歷一次數(shù)組A的方式以查找該元素是否在旋轉數(shù)組A中，時間復雜度為O(n)，這么簡單、直觀的解法顯然不能令面試官滿意，因為沒有利用到旋轉數(shù)組的特性。旋轉數(shù)組實際上可以劃分為兩個已排序的子數(shù)組，而且前面的子數(shù)組的元素都大于或者等于后面子數(shù)組的元素，并且后面子數(shù)組的第一個元素（數(shù)組中的最小元素）剛好是這兩個子數(shù)組的分界線。在已排序的數(shù)組中，通過二分法可以實現(xiàn)O(lgn)的查找，對于旋轉數(shù)組，也可以試著用二分查找法來尋找這個最小的元素。

和二分查找法一樣，用兩個指針分別指向數(shù)組的第一個元素和最后一個元素，根據(jù)旋轉數(shù)組的特性（假設旋轉前的數(shù)組是增序），數(shù)組的第一個元素應該是大于或者等于最后一個元素；接著可以找到數(shù)組中間的元素，如果該中間元素位于前面的遞增子數(shù)組，那它應該大于或者等于第一個指針指向的元素，此時數(shù)組中最小的元素應該位于該中間元素的后面，所以為了縮小范圍，應把第一個指針指向該中間元素，此時，第一個指針仍然位于前面的遞增子數(shù)組中。

同樣，如果中間元素位于后面的遞增子數(shù)組，那它應該小于或者等于第二個指針指向的元素，此時該數(shù)組中最小的元素應該位于該中間元素的前面，為了縮小范圍，應把最后一個指針指向該中間元素，此時，第二個指針仍然位于后面的遞增子數(shù)組中。

由此可見，不管是移動第一個指針還是第二個指針，查找范圍都會縮小到原來的一半，接下來可再用更新后的兩個指針，重復做新一輪的查找。那最終情況會如何呢？因為二分查找法，是不斷地逼近要查找的元素，所以兩個指針會離待查找元素越來越近，所以查找最小元素時，第一個指針會一直在前面遞增的子數(shù)組中，第二個指針會一直在后面遞增的子數(shù)組中，最終情況就是第一個指針會指向數(shù)組中的最大元素（前面子數(shù)組的最后一個元素），第二個指針會指向數(shù)組中的最小元素（后面數(shù)組的第一個元素）。這就是循環(huán)結束的條件！

特例一 - 旋轉數(shù)組未旋轉

旋轉數(shù)組的定義中，是將已排序的數(shù)組的前幾個元素放到最后面，但是，如果是把前0個元素放到最后面，即旋轉數(shù)組未旋轉，此時仍是已排序的數(shù)組，但不再滿足通常旋轉數(shù)組第一個元素大于、等于最后一個元素的情況，而是第一個元素小于最后一個元素。所以，如果發(fā)現(xiàn)第一個元素小于最后一個元素，即可確認旋轉數(shù)組未旋轉，第一個元素即是最小元素。

特例二 - 左、右、中三者元素相等

該問題中，如果第一個指針、第二個指針及中間指針所指向的元素都相等時，無法判斷最小元素位于前面的子數(shù)組還是后面的子數(shù)組中。比如，對于原數(shù)組{0，1，1，1，1，1}來說，數(shù)組{1，0，1，1，1，1}和{1，1，1，1，0，1}都是它的旋轉數(shù)組，若left = 0，right = array.len-1，mid = (left+right)/2，兩個數(shù)組中都有array[left] = array[right] = array[mid]，但最小元素位于不同的子數(shù)組中；一般情況下，通過比較array[mid]和array[left]、array[right]的大小，可以確定array[mid]所處的位置——前面的子數(shù)組或后面的子數(shù)組，但三者相等時，無法再判斷array[mid]的位置，所以無法確定數(shù)組的最小元素在哪一個子數(shù)組中。
所以，在三者相等時，只有采用順序查找的方法，確定最小元素的位置。

源碼

using namespace std;

/*!
 * \brief find_min
 *  找到旋轉數(shù)組中的最小值并返回
 * \param array
 *  旋轉數(shù)組
 * \param len
 *  旋轉數(shù)組長度
 * \return
 *  旋轉數(shù)組中的最小值
 */
int find_min(int* array, int len)
{
    //判斷輸入的有效性
    if(array == NULL || len <= 0)
    {
        cout << "Input Error!"<< endl;
        return -1;
    }

    //特例1，旋轉數(shù)組未旋轉
    if(array[0] < array[len-1])
    {
        cout << "In rotated array, min num is " << array[0] << endl;
        return array[0];
    }

    int left = 0, right = len-1;
    int mid = (left+right)/2;
    //采用二分查找法查找循環(huán)數(shù)組最小數(shù)，結束時left指針
    //指向數(shù)組中的最大值，right指向數(shù)組中的最小值
    while(right-left != 1)
    {
        if(array[left] < array[mid])
        {
            left = mid;
        }
        else if(array[right] > array[mid])
        {
            right = mid;
        }
        //特例2：左、中、右三個元素相等，采用順序查找法
        else if(array[left] == array[mid] && array[mid] == array[right])
        {
            int min = array[left];
            for(int i = left+1; i <= right; i++)
            {
                if(min > array[i])
                {
                    min = array[i];
                }
            }
            cout << "In rotated array, min num is " << min << endl;
            return min;
        }
        mid = (left+right)/2;
    }

    cout << "In rotated array, min num is " << array[right] << endl;
    return array[right];
}

阿里面試 - 在旋轉數(shù)組中查找某個數(shù)

題目

給定一個旋轉數(shù)組A，和一個待查找元素m，如果m在旋轉數(shù)組A中，返回A中該元素的下標；如果m不在旋轉數(shù)組A中，返回-1。

解析

通過上面的分析，可以得到旋轉數(shù)組中的最小值，也可以得到它的下標，通過比較待查找元素與數(shù)組中第一個元素和最后一個元素的大小，確定待查找元素落在哪個子數(shù)組區(qū)間內(nèi)，然后再用二分查找法查找某個區(qū)間，存在就返回它的下表；不存在就返回-1。

源碼

/*!
 * \brief find_min_index
 *  返回旋轉數(shù)組中的最小元素的下標
 * \param array
 *  旋轉數(shù)組
 * \param len
 *  旋轉數(shù)組長度
 * \return
 *  最小元素的下標
 */
int find_min_index(int* array, int len)
{
    //判斷輸入的有效性
    if(array == NULL || len <= 0)
    {
        cout << "Input Error!"<< endl;
        return -1;
    }

    //特例1，旋轉數(shù)組未旋轉
    if(array[0] < array[len-1])
    {
        cout << "In rotated array, min_index is 0" << endl;
        return 0;
    }

    int left = 0, right = len-1;
    int mid = (left+right)/2;
    //采用二分查找法查找循環(huán)數(shù)組最小數(shù)，結束時left指針
    //指向數(shù)組中的最大值，right指向數(shù)組中的最小值
    while(right-left != 1)
    {
        if(array[left] < array[mid])
        {
            left = mid;
        }
        else if(array[right] > array[mid])
        {
            right = mid;
        }
        //特例2：左、中、右三個元素相等，采用順序查找法
        else if(array[left] == array[mid] && array[mid] == array[right])
        {
            int min_index = left;
            for(int i = left+1; i <= right; i++)
            {
                if(array[min_index] > array[i])
                {
                    min_index = i;
                }
            }
            cout << "In rotated array, min_index is " << min_index << endl;
            return min_index;
        }
        mid = (left+right)/2;
    }

    cout << "In rotated array, min_index is " << right << endl;
    return right;
}

/*!
 * \brief binary_search
 *  二分查找算法
 * \param p
 *  待查找數(shù)組
 * \param left
 *  起始查找位置
 * \param right
 *  結束查找位置
 * \param m
 *  待查找元素
 * \return
 *  成功，返回元素下標；失敗，返回-1.
 */
int binary_search(int* p, int start, int end, int num)
{
    int left = start;
    int right = end;
    int mid = (left+right)/2;
    while(right-left != 1)
    {
        if(num > p[mid])
        {
            left = mid;
        }
        else if(num < p[mid])
        {
            right = mid;
        }
        else
        {
            cout << "Find m! Its index is " << mid << endl;
            return mid;
        }
        mid = (left+right)/2;
    }
    if(num != p[right])
    {
        return -1;
    }
    cout << "Find m! Its index is " << right << endl;
    return right;
}

/*!
 * \brief find_num
 *  在旋轉數(shù)組中查找元素m，若數(shù)組中存在該元素，則返回它的下標；
 *  如果不存在，則返回-1.
 * \param p
 *  旋轉數(shù)組指針
 * \param len
 *  旋轉數(shù)組長度
 * \param m
 *  待查找元素
 * \return
 *  成功，返回元素下標；失敗，返回-1.
 */
int find_num(int* p, int len, int m)
{
    if(p == NULL || len < 0)
    {
        return -1;
    }

    int min_index = find_min_index(p, len);

    if(min_index == 0)
    {
        if(m < p[0] || m > p[len-1])
        {
            return -1;
        }
        return binary_search(p, 0, len-1, m);
    }

    if(m < p[min_index] || m > p[min_index-1])
    {
        return -1;
    }
    if(m >= p[0])
    {
        return binary_search(p, 0, min_index-1, m);
    }
    else if(m < p[len-1])
    {
        return binary_search(p, min_index, len-1, m);
    }
}