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

标签：二分法

思路：

• 旋转数组的定义：是由一个本来有序的数组，经过首位元素的旋转交换后得到的数组。
• 则新的数组是分段的保持有序，如从AB变成BA（即数组一定程度上还是有序的）
• 确定新数组的中点、初始起点、初始终点的数组下标

media = len(rotateArray) // 2
start = 0
end = len(rotateArray) - 1

• 移动规律：
  • 如果中点大于右端点，则最小值在右区间。此时需要缩小左界，start=media
  • 如果中点大于左端点，则最小值在左区间。此时需要缩小右界，end=media
  • 如果中点和左端点或右端点都相等，则要进行完整的一轮遍历。依次判断首尾值来缩小start和end值

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        media = len(rotateArray) // 2
        start = 0
        end = len(rotateArray) - 1
        
        if rotateArray[media] > rotateArray[end]:
            start = media + 1
        elif rotateArray[media] < rotateArray[end]:
            end = media
            
        while start != end:
            if rotateArray[end] >= rotateArray[start]:
                end -= 1
            else:
                start += 1
        return rotateArray[start]

参照帖子后做的优化： https://blog.nowcoder.net/n/fe92cdbd3338488b80167913b0be10b7

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        start = 0
        end = len(rotateArray) - 1
        while start < end:
            media = (start + end) // 2
            if rotateArray[media] > rotateArray[end]:
                start = media + 1
            elif rotateArray[media] == rotateArray[end]:
                end -= 1
            else:
                end = media
        return rotateArray[start]