面试题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 << Bi补充：软件开发 , C++ ,
