面試題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 <iostream>   
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 <iostream>
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 <iostream>   
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 <iostream>
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;
}