剑指Offer编程题-旋转数组的最小数字 | 我的个人生活记录

题目：旋转数组的最小数字

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

解题思路

旋转数组为非减排序，那么最小值可以将数组划分为两个非减排序的数组。

• 从前往后、从后往前同时查找
• 二分法查找

实现

python

方法一（复杂度较高）：

-*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        m = 0
        n = len(rotateArray)-1
        mi = rotateArray[0]
        while mrotateArray[m+1]:
                mi = rotateArray[m+1]
                break
            if rotateArray[n-1]>rotateArray[n]:
                mi = rotateArray[n]
                break
            m = m + 1
            n = n - 1
        return mi

二分查找（一）：

-*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        low = 0
        high = len(rotateArray) - 1
        while low < high:
            mid = int((low + high) / 2)
            if rotateArray[mid]>rotateArray[high]:
                low = mid + 1
            elif rotateArray[mid] < rotateArray[low]:
                high = mid
            elif rotateArray[low] == rotateArray[high]:
                low = low + 1
                high = high - 1
            else:
                break
        return rotateArray[low]

二分查找（二）：

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        low = 0
        high = len(rotateArray) - 1
        while low < high-1:
            mid = int((low + high) / 2)
            if rotateArray[mid]>rotateArray[high]:
                low = mid
            elif rotateArray[mid] < rotateArray[low]:
                high = mid
            elif rotateArray[low] == rotateArray[high]:
                low = low + 1
                high = high - 1
            else:
                break
        return rotateArray[low] if rotateArray[low] < rotateArray[high] else rotateArray[high]