旋转数组的最小数字

题目

给定一个递增的旋转数组A，返回旋转数组中的最小值。旋转数组：给定一个已排序的数组，假设为升序，想象数组是一个环形数组，向左或向右拨动数组，即可形成旋转数组。

解析

如果采用遍历一次数组A的方式以查找该元素是否在旋转数组A中，时间复杂度为O(n)，这么简单、直观的解法显然不能令面试官满意，因为没有利用到旋转数组的特性。旋转数组实际上可以划分为两个已排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素，并且后面子数组的第一个元素（数组中的最小元素）刚好是这两个子数组的分界线。在已排序的数组中，通过二分法可以实现O(lgn)的查找，对于旋转数组，也可以试着用二分查找法来寻找这个最小的元素。

和二分查找法一样，用两个指针分别指向数组的第一个元素和最后一个元素，根据旋转数组的特性（假设旋转前的数组是增序），数组的第一个元素应该是大于或者等于最后一个元素；接着可以找到数组中间的元素，如果该中间元素位于前面的递增子数组，那它应该大于或者等于第一个指针指向的元素，此时数组中最小的元素应该位于该中间元素的后面，所以为了缩小范围，应把第一个指针指向该中间元素，此时，第一个指针仍然位于前面的递增子数组中。

同样，如果中间元素位于后面的递增子数组，那它应该小于或者等于第二个指针指向的元素，此时该数组中最小的元素应该位于该中间元素的前面，为了缩小范围，应把最后一个指针指向该中间元素，此时，第二个指针仍然位于后面的递增子数组中。

由此可见，不管是移动第一个指针还是第二个指针，查找范围都会缩小到原来的一半，接下来可再用更新后的两个指针，重复做新一轮的查找。那最终情况会如何呢？因为二分查找法，是不断地逼近要查找的元素，所以两个指针会离待查找元素越来越近，所以查找最小元素时，第一个指针会一直在前面递增的子数组中，第二个指针会一直在后面递增的子数组中，最终情况就是第一个指针会指向数组中的最大元素（前面子数组的最后一个元素），第二个指针会指向数组中的最小元素（后面数组的第一个元素）。这就是循环结束的条件！

特例一 - 旋转数组未旋转

旋转数组的定义中，是将已排序的数组的前几个元素放到最后面，但是，如果是把前0个元素放到最后面，即旋转数组未旋转，此时仍是已排序的数组，但不再满足通常旋转数组第一个元素大于、等于最后一个元素的情况，而是第一个元素小于最后一个元素。所以，如果发现第一个元素小于最后一个元素，即可确认旋转数组未旋转，第一个元素即是最小元素。

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

该问题中，如果第一个指针、第二个指针及中间指针所指向的元素都相等时，无法判断最小元素位于前面的子数组还是后面的子数组中。比如，对于原数组{0，1，1，1，1，1}来说，数组{1，0，1，1，1，1}和{1，1，1，1，0，1}都是它的旋转数组，若left = 0，right = array.len-1，mid = (left+right)/2，两个数组中都有array[left] = array[right] = array[mid]，但最小元素位于不同的子数组中；一般情况下，通过比较array[mid]和array[left]、array[right]的大小，可以确定array[mid]所处的位置——前面的子数组或后面的子数组，但三者相等时，无法再判断array[mid]的位置，所以无法确定数组的最小元素在哪一个子数组中。
所以，在三者相等时，只有采用顺序查找的方法，确定最小元素的位置。

源码

using namespace std;

/*!
 * \brief find_min
 *  找到旋转数组中的最小值并返回
 * \param array
 *  旋转数组
 * \param len
 *  旋转数组长度
 * \return
 *  旋转数组中的最小值
 */
int find_min(int* array, int len)
{
    //判断输入的有效性
    if(array == NULL || len <= 0)
    {
        cout << "Input Error!"<< endl;
        return -1;
    }

    //特例1，旋转数组未旋转
    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;
    //采用二分查找法查找循环数组最小数，结束时left指针
    //指向数组中的最大值，right指向数组中的最小值
    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];
}

阿里面试 - 在旋转数组中查找某个数

题目

给定一个旋转数组A，和一个待查找元素m，如果m在旋转数组A中，返回A中该元素的下标；如果m不在旋转数组A中，返回-1。

解析

通过上面的分析，可以得到旋转数组中的最小值，也可以得到它的下标，通过比较待查找元素与数组中第一个元素和最后一个元素的大小，确定待查找元素落在哪个子数组区间内，然后再用二分查找法查找某个区间，存在就返回它的下表；不存在就返回-1。

源码

/*!
 * \brief find_min_index
 *  返回旋转数组中的最小元素的下标
 * \param array
 *  旋转数组
 * \param len
 *  旋转数组长度
 * \return
 *  最小元素的下标
 */
int find_min_index(int* array, int len)
{
    //判断输入的有效性
    if(array == NULL || len <= 0)
    {
        cout << "Input Error!"<< endl;
        return -1;
    }

    //特例1，旋转数组未旋转
    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;
    //采用二分查找法查找循环数组最小数，结束时left指针
    //指向数组中的最大值，right指向数组中的最小值
    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
 *  待查找数组
 * \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
 *  在旋转数组中查找元素m，若数组中存在该元素，则返回它的下标；
 *  如果不存在，则返回-1.
 * \param p
 *  旋转数组指针
 * \param len
 *  旋转数组长度
 * \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);
    }
}