题目
旋转数组的最小数字这道题来自《剑指Offer》
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序（数字可以重复）的数组的一个旋转，输出旋转数组中的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
思路1：
这道题就是求数组中的最小元素，最简单的办法就是定义一个变量 min 存数组的第一个元素，然后遍历数组和 min 比大小。
C语言代码
int minArray(int* numbers, int numbersSize){
if (numbers == NULL || numbersSize == 0)
{
return -1;
}
int min = numbers[0];
int i = 0;
for (i = 1; i < numbersSize; i++)
{
if (numbers[i] < min)
{
min = numbers[i];
}
}
return min;
}
Java代码
class Solution {
public int minArray(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int min = numbers[0];
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] < min) {
min = numbers[i];
}
}
return min;
}
}
这种解法时间复杂度为O(n),显然这种解法效率太低了，而且并没有体现出旋转数组的特性。
思路2：
我们可以使用双指针的解法，因为该数组是非递减的，那么相邻两个元素，前面的元素要么是小于后面的元素，要么就是等于后面的元素。但如果前面的元素大于后面的元素，那么后面的元素就是要找的最小值。当然还要考虑到数组全部旋转了的情况，也就是相当于没有旋转
C语言代码
int minArray(int* numbers, int numbersSize){
if (numbers == NULL || numbersSize == 0)
{
return -1;
}
int start = 0;
int end = 1;
while (end < numbersSize)
{
if (numbers[start] > numbers[end])
{
return numbers[end];
}
start++;
end++;
}
//走到这里说明数组相当于没有旋转
return numbers[0];
}
Java代码
class Solution {
public int minArray(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int start = 0;
int end = 1;
while (end < numbers.length) {
if (numbers[start] > numbers[end])
{
return numbers[end];
}
start++;
end++;
}
//走到这里说明，数组第一个元素就是最小的
return numbers[0];
}
}
思路2其实和思路1类似，都属于遍历数组。但思路2效率会高那么一点，但如果数组只是旋转一次，那么思路2也是要遍历整个数组的。或数组全部旋转了一遍又变成了{1,2,3,4,5},同样也要遍历整个数组。
思路3：
我们发现每次旋转后的数组可以分成左右两个递增序列，前面的序列是要大于或者等于后面的子序列的，而且最小的元素正好是左右两个子序列的分界线。对于有序的数组我们可以使用二分查找的方式来进行查找。
我们定义一个 left 和 right 分别表示数组的最左边的元素和最右边的元素，mid表示中间的下标，
1.我们发现当 mid 大于 最左边值 left的时候，说明mid属于前半部分的序列，要找的最小元素就在mid的右边
2.当 mid值小于左边值 left的时候，说明mid此时属于后半部分的序列，那么要找的值就是在mid的左边
根据上面的分析我们就能总结出
当 array[left] <= array[mid]时，让 left = mid
当 array[left] > array[mid]时,让 right = mid
这样一次砍掉一半，[left,right] 区间就会不断缩小，这个过程中 left 一直是数组的前半部分， right 一直是数组的后半部分。
根据旋转数组的规则，当 left 和 right 相邻时，那么right就是最小的那个元素。因为left的值始终是要大于right也就是后半部分的值，此时left相当于前半部分最大的值，right就是后半部分最小的值。
还有一个难点就是，这个数组的元素是可以重复的，那么就可能出现以下情况
在这两种情况下，第一个指针和第二个指针指向的数字都是1，并且两个指针中间的数字也是1，左右中间的三个数都相同。
第一种情况，中间数字下标为2，位于后面的子数组；
第二种情况，中间数字下标为2，位于前面的子数组中。
所以当left、right、mid的数都相同的时候，我们就无法判断中间的数字是位于前半部分还是后半部分，也就无法缩小 left 和
right 之间的距离。 所以这道题还得进行判断 left、right、mid 是否相等，如果相等就不得不采取顺序查找的方式了。
C语言代码
int minArray(int* numbers, int numbersSize){
if (numbers == NULL || numbersSize == 0)
{
return -1;
}
int left = 0;
int right = numbersSize-1;
int mid = 0;
while (numbers[left] >= numbers[right])
{
//判断left和right是否相邻
if (right-left == 1)
{
mid = right;
break;
}
mid = left+((right-left)>>1);
//判断left mid right 是否相等
if (numbers[left] == numbers[mid] && numbers[mid] == numbers[right])
{
//left和right相等所以没必要取 <=
int result = numbers[left];
int i = 0;
for (i = left+1; i < right; i++)
{
//如果比最小值还要小就更新
if (numbers[i] < result)
{
result = numbers[i];
}
}
//遍历完后之间return;
return result;
}
if (numbers[mid] >= numbers[left])
{
//说明mid在前半部分
left = mid;
}else if (numbers[mid] < numbers[left])
{
//说明mid属于后半部分
right = mid;
}else{
//说明mid就是最小值
break;
}
}
return numbers[mid];
}
Java代码
class Solution {
public int minArray(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int left = 0;
int right = numbers.length-1;
int mid = 0;
//因为是旋转数组，前半部分的元素的值一定是大于后半部分的
//如果不满足条件说明该数组的元素全部旋转了一遍
while (numbers[left] >= numbers[right]) {
//判读left和right是否相邻
if (right-left == 1) {
mid = right;
break;
}
mid = left+((right-left)>>1);
//判断left right mid 是否相等
if (numbers[left] == numbers[mid] && numbers[mid] == numbers[right]) {
int result = numbers[left];
for (int i = left+1; i < right; i++) {
if (result > numbers[i]) {
result = numbers[i];
}
}
return result;
}
if (numbers[mid] >= numbers[left]) {
//说明mid属于前半部分，那么要找的值就在后半部分
left = mid;
}else if (numbers[mid] < numbers[left]) {
//说明mid属于后半部分，那么要找的值就在前半部分
right = mid;
}else{
break;
}
}
return numbers[mid];
}
}
题目链接 旋转数组的最小数字