面试题8：旋转数组中的最小数字

旋转数组的特点：

（1）递增排序的数组旋转之后的数组可划分为两个排序的子数组；

（2）前面的子数组的元素都大于或等于后面子数组的元素；

（3）最小的元素刚好是两个子数组的分界线；

（4）旋转数组在一定程度上是有序的；

?????? 在有序的数组中可以用二分查找实现O(logn)的查找，我们也可用二分查找的思想寻找旋转数组的最小数字。

思路：

1. 设置两个指针，初始状态第一个指针指向前面子数组的第一个元素，第二个指针指向后面子数组的最后一个元素；

2. 找到两个指针的中间元素；

3.若其大于等于第一个指针指向的元素，则说明其在前面的子数组中，且显然最小元素在中间元素的右边，若其小于等于第二个指针指向的元素，则说明其在后面的子数组中，且显然最小元素在中间元素的左边。

如此，便可以缩小搜索范围，提高时间复杂度，最终第一个指针指向前面子数组的最后一个元素，而第二个指针指向后面子数组的第一个元素，它们处于相邻位置，而第二个指针指向的刚好是最小的元素。

注意：当两个指针指向的数字及它们中间的数字三者相等时，无法判断中间数字位于前面的子数组还是后面的子数组，也就无法移动两个指针来缩小查找的范围，此时只能用顺序查找的方法。

例如：数组{1,0,1,1,1}和数组{1,1,1,0,1}都可看成是递增数组{0,1,1,1,1}的旋转。第一种情况，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。

?

?

（5）按旋转规则，第一个元素应该是大于或等于最后一个元素的；

????? 但也有特例：若把排序数组的前0个元素搬到最后面，及排序数组本身，仍是数组的一个旋转，此时数组中的第一个数字是最小的数字。

?

?

C++代码（不完全正确）：

#include "stdafx.h"   
#include    
using namespace std;  
  
int BinarySearch_MinNumInRotateArr(int *nArr, int nLength)  
{  
    if (nArr!=NULL && nLength>0)  
    {  
       int low = 0;  
       int high = nLength - 1;  
       int mid = 0;  
  
       while ((low+1) != high)  
       {  
           mid = low + ((high - low) >> 1);  
  
           if (nArr[low] == nArr[high] && nArr[low] == nArr[mid])  
           {  
               int min = nArr[low];  
               for (int i=low+1; i<=high; i++)  
               {  
                  if (min > nArr[i])  
                  {  
                      min = nArr[i];  
                  }  
               }  
               return min;  
           }  
  
           if (nArr[mid] >= nArr[low])  
           {  
               low = mid;  
           }  
           else if (nArr[mid] <= nArr[high])  
           {  
               high = mid;  
           }  
       }  
       return nArr[high];  
    }  
    else  
    {  
        cout << "数组为空！" << endl;  
        return -1;  
    }  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int nArr1[5] = {3,4,5,1,2};  
    cout << BinarySearch_MinNumInRotateArr(nArr1, 5) << endl;  
    int nArr2[5] = {1,0,1,1,1};  
    cout << BinarySearch_MinNumInRotateArr(nArr2, 5) << endl;  
    int nArr3[5] = {1,1,1,0,1};  
    cout << BinarySearch_MinNumInRotateArr(nArr3, 5) << endl;  
    int nArr4[5] = {1,2,3,4,5};//特例没有正确返回结果   
    cout << BinarySearch_MinNumInRotateArr(nArr4, 5) << endl;  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include 
using namespace std;

int BinarySearch_MinNumInRotateArr(int *nArr, int nLength)
{
	if (nArr!=NULL && nLength>0)
	{
       int low = 0;
	   int high = nLength - 1;
       int mid = 0;

       while ((low+1) != high)
       {
		   mid = low + ((high - low) >> 1);

		   if (nArr[low] == nArr[high] && nArr[low] == nArr[mid])
		   {
			   int min = nArr[low];
			   for (int i=low+1; i<=high; i++)
			   {
                  if (min > nArr[i])
                  {
					  min = nArr[i];
                  }
			   }
			   return min;
		   }

		   if (nArr[mid] >= nArr[low])
		   {
			   low = mid;
		   }
		   else if (nArr[mid] <= nArr[high])
		   {
			   high = mid;
		   }
       }
	   return nArr[high];
	}
	else
	{
		cout << "数组为空！" << endl;
		return -1;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nArr1[5] = {3,4,5,1,2};
	cout << BinarySearch_MinNumInRotateArr(nArr1, 5) << endl;
	int nArr2[5] = {1,0,1,1,1};
	cout << BinarySearch_MinNumInRotateArr(nArr2, 5) << endl;
	int nArr3[5] = {1,1,1,0,1};
	cout << BinarySearch_MinNumInRotateArr(nArr3, 5) << endl;
	int nArr4[5] = {1,2,3,4,5};//特例没有正确返回结果
	cout << BinarySearch_MinNumInRotateArr(nArr4, 5) << endl;
	system("pause");
	return 0;
}

不能解决特例数组。

C++代码（正确解决特例）：

 
#include "stdafx.h"   
#include    
using namespace std;  
  
int BinarySearch_MinNumInRotateArr(int *nArr, int nLength)  
{  
    if (nArr!=NULL && nLength>0)  
    {  
        int low = 0;  
        int high = nLength - 1;  
        int mid = low;  
  
        while (nArr[low] >= nArr[high])  
        {  
            if (high - low == 1)  
            {  
                mid = high;  
                break;  
            }  
  
            mid = low + ((high - low) >> 1);  
  
            if (nArr[low] == nArr[high] && nArr[low] == nArr[mid])  
            {  
                int min = nArr[low];  
                for (int i=low+1; i<=high; i++)  
                {  
                    if (min > nArr[i])  
                    {  
                        min = nArr[i];  
                    }  
                }  
                return min;  
            }  
  
            if (nArr[mid] >= nArr[low])  
            {  
                low = mid;  
            }  
            else if (nArr[mid] <= nArr[high])  
            {  
                high = mid;  
            }  
        }  
        return nArr[mid];  
    }  
    else  
    {  
        cout << "数组为空！" << endl;  
        return -1;  
    }  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int nArr1[5] = {3,4,5,1,2};  
    cout << BinarySearch_MinNumInRotateArr(nArr1, 5) << endl;  
    int nArr2[5] = {1,0,1,1,1};  
    cout << BinarySearch_MinNumInRotateArr(nArr2, 5) << endl;  
    int nArr3[5] = {1,1,1,0,1};  
    cout << BinarySearch_MinNumInRotateArr(nArr3, 5) << endl;  
    int nArr4[5] = {1,2,3,4,5};  
    cout << BinarySearch_MinNumInRotateArr(nArr4, 5) << endl;  
    int *nArr5 = NULL;  
    cout << BinarySearch_MinNumInRotateArr(nArr5, 5) << endl;  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include 
using namespace std;

int BinarySearch_MinNumInRotateArr(int *nArr, int nLength)
{
	if (nArr!=NULL && nLength>0)
	{
		int low = 0;
		int high = nLength - 1;
		int mid = low;

		while (nArr[low] >= nArr[high])
		{
			if (high - low == 1)
			{
				mid = high;
				break;
			}

			mid = low + ((high - low) >> 1);

			if (nArr[low] == nArr[high] && nArr[low] == nArr[mid])
			{
				int min = nArr[low];
				for (int i=low+1; i<=high; i++)
				{
					if (min > nArr[i])
					{
						min = nArr[i];
					}
				}
				return min;
			}

			if (nArr[mid] >= nArr[low])
			{
				low = mid;
			}
			else if (nArr[mid] <= nArr[high])
			{
				high = mid;
			}
		}
		return nArr[mid];
	}
	else
	{
		cout << "数组为空！" << endl;
		return -1;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nArr1[5] = {3,4,5,1,2};
	cout << BinarySearch_MinNumInRotateArr(nArr1, 5) << endl;
	int nArr2[5] = {1,0,1,1,1};
	cout << BinarySearch_MinNumInRotateArr(nArr2, 5) << endl;
	int nArr3[5] = {1,1,1,0,1};
	cout << BinarySearch_MinNumInRotateArr(nArr3, 5) << endl;
	int nArr4[5] = {1,2,3,4,5};
	cout << BinarySearch_MinNumInRotateArr(nArr4, 5) << endl;
	int *nArr5 = NULL;
	cout << BinarySearch_MinNumInRotateArr(nArr5, 5) << endl;
	system("pause");
	return 0;
}

?