在有序旋转数组中找到最小值

题目

　　有序数组arr可能经过一次旋转处理，也可能没有，且arr可能存在重复的数。例如，有序数组[1,2,3,4,5,6,7]，可以旋转处理成[4,5,6,7,1,2,3]等。给定一个可能旋转过的有序数组arr，返回arr中的最小值。

基本思路

　　尽可能的利用二分查找，但是最坏情况仍然无法避免O(N)的时间复杂度。首先需要知道，如果一个有序数组经过旋转后，最小的值一定是数组中降序的那个位置，其余部分都是升序。同时，数组的第一个元素一定比最后一个元素大。如果没有经过旋转，数组整体都是升序，最小值就是数组的第一个值。

　　所以在利用二分查找的时候，如果arr[left] < arr[right]，说明数组整体升序，直接返回arr[left]。否则，如果arr[left] > arr[mid]，说明降序一定发生在数组左半区，令right = mid；如果arr[mid] > arr[right]，说明降序一定发生在数组右半区，令left = mid。

　　但是有一个很重要的问题，在arr数组中可能存在重复的值，那么就可能发生arr[left] == arr[mid] == arr[right]的情况。这个时候，我们从left位置开始，向右遍历，假设遍历到位置i，如果arr[i] == arr[mid]，继续向右遍历；如果arr[i] > arr[mid]，说明降序一定发生在arr[i…mid]之间，令left = i，right = mid；如果arr[i] < arr[mid]，说明此时出现了降序，直接返回arr[i]即可。如果遍历到mid位置都一直与arr[mid]相等，说明左半区都是一个值，所以降序一定出现在右半区，所以令left = mid。

　　最坏的情况下，所有的值都是一个值。对于每个值都需要遍历一遍，所以最坏的时间复杂度是O(N)。

def getMin(arr):
    low = 0
    high = len(arr) - 1

    while low < high:

        if low == hight - 1:
            break

        if arr[low] < arr[high]:
            return arr[low]

        mid = (low + high)//2

        if arr[mid] < arr[low]:
            high = mid
            continue

        elif arr[mid] > arr[high]:
            low = mid
            continue
        
        while low < mid:
            if arr[low] == arr[mid]:
                low +=1
            elif arr[low] < arr[mid]:
                return arr[low]
            else:
                high = mid
                break

    return min(arr[left],arr[right])