【剑指offer】07-旋转数组中的最小数字

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        """利用二分查找"""
        n = len(rotateArray)
        first = 0
        last = n-1
        # 先要考虑题目中的特殊情况
        if not rotateArray:
            return 0
        if n == 1:
            return rotateArray[first]
        while first <= last:
            mid = (first + last) // 2
            # 先看找到最小值 是什么个情况
            if rotateArray[mid] < rotateArray[mid-1]:
                # 如果mid刚好比前面那个值小，说明mid就是最小值，∵是非递减数列
                return rotateArray[mid]
            elif rotateArray[mid] < rotateArray[last]:
                # 如果mid比最后小，说明最小值在mid的左边，last游标就移动到现在mid的前面一个
                last = mid - 1
            else:
                first = mid + 1
        return 0


if __name__ == ‘__main__‘:
    S = Solution()
    # 用例1：正常数组
    print(S.minNumberInRotateArray([3, 4, 5, 1, 2]))
    # 用例2：正常数组，有重复数字
    print(S.minNumberInRotateArray([4, 4, 5, 1, 2, 3]))
    # 用例3：边界值：升序数组
    print(S.minNumberInRotateArray([3, 4, 5, 6, 7, 9]))
    # 用例4：边界值：只有一个数字的数组
    print(S.minNumberInRotateArray([9]))
    # 用例5：特殊：空数组
    print(S.minNumberInRotateArray([]))

def minValueRotateArray(rotateArray):
     
    if rotateArray == []:
        return 0
    left=0
    right = len(rotateArray)-1
    while left != right and left != right-1:
        if rotateArray[left] > rotateArray[right]:
            temp = int((left+right)/2)
            if rotateArray[temp] >= rotateArray[left]:
                left = temp
            else :
                right = temp
        elif rotateArray[left] == rotateArray[right]:
            temp = right-1
            if rotateArray[temp] > rotateArray[left]:
                left = temp
            else :
                right = temp
        else :
            temp = int((left+right)/2)
            if rotateArray[temp] > rotateArray[left]:
                right = temp
            else :
                left = temp
    if rotateArray[left] > rotateArray[right]:
        return rotateArray[right]
    else :
        return rotateArray[left]
 
if __name__ == ‘__main__‘:
    listx = input()
    listy = []
    for ix in listx.split(‘ ‘):
        listy.append(int(ix))
    minValue = minValueRotateArray(listy)
    print(minValue)