题解 | #旋转数组的最小数字#

二分法对于部分有序的数据可以直接进行考虑判断，能够减少时间复杂度

class Solution:
    def minNumberInRotateArray2(self , rotateArray: List[int]) -> int:
        # write code here按照题意直接对相关的数据进行计算就可，但由于时间复杂度的要求，需要使用二分法进行数据的查找
        data_min = rotateArray[0]
        for i in rotateArray:
            
            if data_min>i:
                data_min = i
        return data_min
    # 但这个题目需要使用二分查找进行求解，原来的数据是有序的，可以使用分治的想法进行求解
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        left = 0
        right = len(rotateArray) -1 
        # 使用双游标进行记录判断
        while left<right:
            mid = int((left + right)/2) # 记录两边有序的数据的中间值
            if rotateArray[mid] > rotateArray[right]:
                # 如果最小的数字在中间数字的右边
                left = mid + 1 # 改变左边的游标继续寻找
            elif rotateArray[mid] == rotateArray[right]:
                right = right- 1  #一个一个进行判断
            else:
                # 其他相等的情况，
                right = mid
        return rotateArray[left]