//旋转数组中的最小数字
//题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转，输入一个递增排序的数组，数组旋转数组的最小元素。
//遍历数组一次，找出最小，效率为O（n），显然不是我们想要的结果
//旋转数组特性：1.可能为两个递增的数组，找出较小数组中的开头的那个就是要求输入的元素
//2.既然为排序好的，那我们可不可以尝试一下二分法去查找呢
int Min(int *number, int length)
{
if (number == NULL || length < 0)
{
throw new std::exception("Invalid paramenters.");
}
int index1 = 0;
int index2 = length - 1;
int indexMid = index1;
//二分查找
while (number[index1] >= number[index2])
{
if (index1 - index2 == 1)
{
indexMid = index2;
break;
}
indexMid = (index1 + index2) / 2;
if (number[index1] == number[index2] && number[indexMid] == number[index2])
{
return MinInorder(number, index1, index2);
}
if (number[indexMid] <= number[index1])
{
index1 = indexMid;//为什么不需要调整为index1=indexMid-1;因为IndexMid有可能就为所求的最小元素，若-1调整后，跳过了最小值。结果肯定是错的
}
else if (number[indexMid]<=number[index2])
{
index2 = indexMid;
}
}
return number[indexMid];
}
int MinInorder(int number[], int index1, int index2)
{
for (int i = index1; i < index2; ++i)
{
if (number[i] < number[index1])
{
return number[i];
}
}
return number[index1];
}
