剑指Offer - 面试题11：旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素，例如，数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

分析

暴力法
我们不考虑任何特点，直接一次循环求解。
C

#include<stdio.h>
#include<stdlib.h>

int Min(int* n, int length)
{
	int min = INT_MAX;
	int i = 0;
	for (i = 0; i < length; i++)
	{
		if (n[i] < min)
		{
			min = n[i];
		}
	}

	return min;
}

int main()
{
	int p[5] = { 3,4,5,1,2 };
	int size = 5;
	int ret = Min(p, size);
	printf("最小值为：%d\n", ret);

	return 0;
}

二分法
我们可以将这个旋转过后的数组，分成俩个递增子数组。

但是还存在一种特殊情况旋转后的数组和原数组相同

总共有俩种情况

• 旋转后数组与原数组不相同
• 旋转后数组与原数组相同

设置start、end指针分别指向数组左右俩边，然后选取中间值mid = ((end - start)>>1 + start),防止溢出。
我们先选start指针做判断位置：

• n[start] < n[mid] 在情况一中，mid位于左递增子数组，在情况二中mid位于右递增数组，所以我们换判断点

选end指针做判断位置：

• n[end] < n[mid] 在情况一中，mid位于左递增子数组。在情况二中，不存在这种
  

• n[end] > n[mid] 在情况一中，mid位于右递增子数组。在情况二中，mid位于右递增子数组
  
  

• n[end] = n[[mid] 在情况一中，mid位于右递增子数组。在情况二中，mid位于右递增子数组。
  
  
  C

#include<stdio.h>
#include<stdlib.h>
int Min(int* n, int length)
{
	if (n == NULL || length <= 0)
	{
		perror("");
		exit(EXIT_FAILURE);
	}
	int start = 0;
	int end = length - 1;

	while (start < end)
	{
		int mid = ((end - start) >> 1) + start;
		if (n[end] < n[mid])
		{
			start = mid + 1;
		}
		else if (n[end] > n[mid])
		{
			end = mid;
		}
		else
		{
			end--;
		}
	}
	return n[start];
}

int main()
{
	int n[10][5] = {
					{1,2,3,4,5},
					{2,3,4,5,1},
					{3,4,5,1,2},
					{4,5,1,2,3},
					{5,1,2,3,4},
					{1,1,1,2,2},
					{1,1,2,2,1},
					{1,2,2,1,1},
					{2,2,1,1,1},
					{1,1,2,2,2}, };
	int i = 0;
	for(i = 0; i< 10;i++)
	{
		int ret = Min(n[i],5);
		printf("min = %d\n", ret);
	}
	return 0;
}

最坏情况就是{1，1，1，1，1}；相当于O(n)的时间复杂度，空间复杂度是常量O(1);
最好情况时间复杂度就是O(long2^N),空间复杂度是常量O(1);
我们也可以让n[end] = n[[mid] 相等时候直接遍历start到end 线性查找

#include<stdio.h>
#include<stdlib.h>
int Min(int* n, int length)
{
	if (n == NULL || length <= 0)
	{
		perror("");
		exit(EXIT_FAILURE);
	}
	int start = 0;
	int end = length - 1;

	while (start < end)
	{
		int mid = ((end - start) >> 1) + start;
		if (n[end] < n[mid])
		{
			start = mid + 1;
		}
		else if (n[end] > n[mid])
		{
			end = mid;
		}
		else
		{
			int m = start;//保存最小值小标
			for (++start; start < end; ++start)
			{
				if (n[m] > n[start])
				{
					m = start;
				}
			}
			return n[m];
		}
	}
	return n[start];
}

int main()
{
	int n[10][5] = {
					{1,2,3,4,5},
					{2,3,4,5,1},
					{3,4,5,1,2},
					{4,5,1,2,3},
					{5,1,2,3,4},
					{1,1,1,2,2},
					{1,1,2,2,1},
					{1,2,2,1,1},
					{2,2,1,1,1},
					{1,1,2,2,2}, };
	int i = 0;
	for(i = 0; i< 10;i++)
	{
		int ret = Min(n[i],5);
		printf("min = %d\n", ret);
	}
	return 0;
}

本章完！