/*************************************************************************
> File Name: 06_MinNumberInRotatedArray.c
> Author: Juntaran
> Mail: [email protected]
> Created Time: 2016年08月29日 星期一 20时14分22秒
************************************************************************/ #include <stdio.h>
#include <stdlib.h> // O(n)解法
int minNumberInRotatedArray1(int* rotatedArray, int length)
{
if (length <= )
return ; for (int i = ; i < length; ++i)
{
if ( rotatedArray[i] < rotatedArray[i-])
return rotatedArray[i];
}
return rotatedArray[];
} // O(log(n))解法
int minNumberInRotatedArray2(int* rotatedArray, int length)
{
if (length <= )
return ;
if (length == )
return rotatedArray[];
int left = ;
int right = length - ;
int middle = ; if (rotatedArray[left] < rotatedArray[right])
return rotatedArray[]; while (rotatedArray[left] >= rotatedArray[right])
{
if (right - left == )
{
middle = right;
break;
}
middle = (left + right) / ; // 如果left、right、middle的值相同，只能顺序查找
if (rotatedArray[left]==rotatedArray[middle]
&& rotatedArray[middle]==rotatedArray[right])
{
for (int i = left+; i < right; ++i)
{
if (rotatedArray[i] < rotatedArray[i-])
return rotatedArray[i];
}
return rotatedArray[left];
} if (rotatedArray[middle] >= rotatedArray[left])
left = middle;
else if (rotatedArray[middle] <= rotatedArray[right])
right = middle;
}
return rotatedArray[middle];
} int main()
{
int rotatedArray1[] = {,,,,,,};
int rotatedArray2[] = {,,,,,,};
int rotatedArray3[] = {,,,,,,};
int rotatedArray4[] = {,,,,,,,,,}; int length1 = ;
int length2 = ; int ret1, ret2; ret1 = minNumberInRotatedArray1(rotatedArray1, length1);
ret2 = minNumberInRotatedArray2(rotatedArray1, length1);
printf("ret1 is %d, ret2 is %d\n", ret1, ret2);
ret1 = minNumberInRotatedArray1(rotatedArray2, length1);
ret2 = minNumberInRotatedArray2(rotatedArray2, length1);
printf("ret1 is %d, ret2 is %d\n", ret1, ret2);
ret1 = minNumberInRotatedArray1(rotatedArray3, length1);
ret2 = minNumberInRotatedArray2(rotatedArray3, length1);
printf("ret1 is %d, ret2 is %d\n", ret1, ret2);
ret1 = minNumberInRotatedArray1(rotatedArray4, length2);
ret2 = minNumberInRotatedArray2(rotatedArray4, length2);
printf("ret1 is %d, ret2 is %d\n", ret1, ret2); return ;
}