剑指Offer的学习笔记（C#篇）-- 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

一 . 方法分析（正常单调递增数组）

1 . 参考二分查找法，我们用两个指针分别指向数组的第一个元素和最后一个元素。

　　2 . 基于二分查找法的概念，找到数组中间的元素：因为该题目是查找旋转数组中的最小值。

如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。

如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。

　　3 . 接下来我们再用更新之后的两个指针，重复做新一轮的查找。

可参考下例：

1. 确定P_mid为5，P_mid>P1且P_mid>P2，说明P1到P_mid为单增。

2. 把P_mid定义为P1，新的P_mid为1，这时候P_mid<P1且P_mid<P2，说明P_mid到 P2是单增，把新的P_mid定义为P2。

3. 这时候P1>P2，且位置相差为1，结束，得出最小数为P2。

二 . 特殊条件

1 . 鲁棒判断：即数组长度为0或者为空数组时，应返回0.

2 . 存在相等的数。

例：

1. 有重复数字，并且重复的数字刚好的最小的数字。 { 3, 4, 5, 1, 1, 2 }

2. 有重复数字，但重复的数字不是第一个数字和最后一个数字。 { 3, 4, 5, 1, 2, 2 }

3. 单调升序数组，旋转0个元素，也就是单调升序数组本身。{ 1, 0, 1, 1, 1 }

4. 数组中只有一个数字。{ 1 }

适当的采用顺序查找法。太晚了，明天写吧！！

三 . 代码实现

class Solution
{
    public int minNumberInRotateArray(int[] rotateArray)
    {
        // write code here
        //鲁棒判断
        if(rotateArray == null || rotateArray.Length <= 0)
        {
            return 0;
        }
        //定义三个参数，用于后期的指针
        int a = 0;
        int b = rotateArray.Length - 1;
        int mid = 0;
        //while终止条件（每次前者大于后者的时候均要对比，当二者差一个数据位时终止返回）
        while(rotateArray[a]>=rotateArray[b])
        {
            if(b - a == 1)
            {
                mid = b;
                break;
            }
        //二分查找法，对mid参数的修改
        mid = (b+a)/2;
        //特殊情况，特殊对待（即数列中存在相等参数时，就采用顺序查找法）
        if(rotateArray[a] == rotateArray[mid] && rotateArray[mid] == rotateArray[b])
        {
            int min = rotateArray[a];
            for(int i = 0;i<rotateArray.Length-1;i++)
            {
                if(min<rotateArray[i])
                {
                    min = rotateArray[i];
                }
            }
        }
        //二分查找法，前后指针的修改
        if(rotateArray[mid]>=rotateArray[a])
        {
            a = mid;
        }
        if(rotateArray[mid]<=rotateArray[b])
        {
            b = mid;
        }
        }
        //返回最小值
        return rotateArray[mid];
    }
}