题目：https://www.nowcoder.com/ta/coding-interviews

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思考：

利用旋转数组的特性来设计查找最小值的方法。

原数组是非递减排序的，旋转数组可划分为两个非递减子数组，并且前面子数组的元素都>=后面子数组的元素，最小元素恰好是两个数组的分界线；

暴力的o(n)查找

1
2
3
4
5
6
7
8
9
10
class Solution1:
    def minNumberInRotateArray(self, rotateArray):
        min = rotateArray[0]
        if len(rotateArray)==0:
            return 0 
        else:
            for i in range(1,len(rotateArray)):
                if rotateArray[i] < min:
                    min = rotateArray[i]
            return min
1
2
3
rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution1()
method.minNumberInRotateArray(rotateArray)
1
1
2
3
4
# for i in range(0,5):#不会包含最后一个索引，左闭右开
#     print(i)
# for i in range(0,len(rotateArray)):
#     print(rotateArray[i])

根据旋转数组的特性设计二分查找:

1.设置中间点，标记旋转数组首元素和尾元素，中间点将数组分成两半;

2.如果中间点大于等于首元素，说明最小数字在数组后一半，如果中间点小于等于尾元素，说明最小数字在数组前一半;

3.依次改变首、尾元素的位置，当尾元素和首元素挨着的时候，这时候尾元素就是所找的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution2:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray)-1
        if len(rotateArray)==0:
            return 0
        else:
            while(right - left) > 1:
                mid = (left + right)//2#商向下取整的结果
                if rotateArray[mid] >= rotateArray[left]:#中间值在第一组比左大，最小值在mid右
                    left = mid#更新左 
                elif rotateArray[mid] <= rotateArray[right]:#中间值在第二组比右小，最小值在mid左
                    right = mid#更新右
            return rotateArray[right]#右元素为最小
            #当不满足while条件时，说明数组有两个元素（或者一个元素），直接返回旋转数组右边元素即可
1
2
3
rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution2()
method.minNumberInRotateArray(rotateArray)
1

特殊的是，当首元素等于尾元素等于中间值时，以上比较规则失效，只能对数组进行顺序查找，增加如下判断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution3:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray)-1
        if len(rotateArray)==0:
            return 0
        else:
            while(right - left) > 1:
                mid = (left + right)//2#商向下取整的结果
                if rotateArray[mid] == rotateArray[left] and rotateArray[mid] == rotateArray[right]:
                    #特殊情况，当首元素等于尾元素等于中间值时，只能对数组进行顺序查找
                    min = rotateArray[left]
                    for i in range(left,right):
                        if rotateArray[i] < min:
                            min = rotateArray[i]
                    return min 
                elif rotateArray[mid] >= rotateArray[left]:#中间值在第一组比左大，最小值在mid右
                    left = mid#更新左 
                elif rotateArray[mid] <= rotateArray[right]:#中间值在第二组比右小，最小值在mid左
                    right = mid#更新右
            return rotateArray[right]#右元素为最小
            #当不满足while条件时，说明数组有两个元素（或者一个元素），直接返回旋转数组右边元素即可
1
2
3
4
# rotateArray = [4, 5, 6, 1, 2, 3]
rotateArray = [ 0, 1, 1]
method = Solution3()
method.minNumberInRotateArray(rotateArray)
1

剑指offer书中还考虑到旋转数组旋转了0个元素的情况，也就是排序数组本身:第一个元素（左）就是最小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray)-1
        if len(rotateArray)==0:
            return 0
        elif rotateArray[left] < rotateArray[right]:
            return rotateArray[left]
        else:
            while(right - left) > 1:
                mid = (left + right)//2#商向下取整的结果
                if rotateArray[mid] == rotateArray[left] and rotateArray[mid] == rotateArray[right]:
                    #特殊情况，当首元素等于尾元素等于中间值时，只能对数组进行顺序查找
                    min = rotateArray[left]
                    for i in range(left,right):
                        if rotateArray[i] < min:
                            min = rotateArray[i]
                    return min 
                elif rotateArray[mid] >= rotateArray[left]:#中间值在第一组比左大，最小值在mid右
                    left = mid#更新左 
                elif rotateArray[mid] <= rotateArray[right]:#中间值在第二组比右小，最小值在mid左
                    right = mid#更新右
            return rotateArray[right]#右元素为最小
            #当不满足while条件时，说明数组有两个元素（或者一个元素），直接返回旋转数组右边元素即可
1
2
3
4
5
6
rotateArray = [  0, 1,  1, 1]
# rotateArray = [ 1, 0, 1,  1, 1,]
# rotateArray = [ 1, 1, 1, 0, 1]
# rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution()
method.minNumberInRotateArray(rotateArray)
0

这里补充另一位博主的写法Solution4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# -*- coding:utf-8 -*-
class Solution4:
    def minNumberInRotateArray(self, rotateArray):
        p1, p2 = 0, len(rotateArray) - 1#一样的操作固定首尾
        mid = p1#特殊情况下的最小值索引，即对应之前的旋转为0的旋转数组。结合下列循环条件来看，我觉得这里很精彩
        while rotateArray[p1] >= rotateArray[p2]:#和之前用索引大小来确定循环不同，这里直接用首元素>=尾元素这个特性来确定循环
            if p2 - p1 == 1:#首尾相邻，尾小，即为最小值
                mid = p2#最后统一返回mid索引下的元素
                break
#             mid = (p1 + p2) / 2#原博主写法
            mid = (p1 + p2) // 2#这里我觉得应该是取整才对
            if rotateArray[mid] == rotateArray[p1] and rotateArray[mid] == rotateArray[p2]:
                return self.minInOrder(rotateArray, p1, p2)#特殊情况，判断失效，只能遍历
            if rotateArray[mid] >= rotateArray[p1]:
                p1 = mid
            elif rotateArray[mid] <= rotateArray[p2]:
                p2 = mid
        return rotateArray[mid]#最终p2会停留在mid上,写作rotateArray[p2]也没有区别，这里整段代码都统一返回mid索引值

    def minInOrder(self, nums, index1, index2):#确定首尾，遍历一段数组，得到最小值
#         n1 = nums[index]#原博主写法
        n1 = nums[index1]#应改为
        for i in range(index1 + 1, index2):
            if n1 > nums[i]:
                return nums[i]
        return n1
1
2
3
4
5
6
# rotateArray = [ 0, 1, 1, 1]
# rotateArray = [ 1, 0, 1,  1, 1]
# rotateArray = [ 1, 1, 1, 0, 1]
rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution4()
method.minNumberInRotateArray(rotateArray)
1

参考：

https://blog.csdn.net/Datawhale/article/details/82143776

https://blog.csdn.net/fuxuemingzhu/article/details/79501202