本文共 1618 字，大约阅读时间需要 5 分钟。

【思路1】本质就是求解数组最小值

class Solution:    def minArray(self, numbers: List[int]) -> int:        return min(numbers)

【思路2】二分法

由于原始数组是递增，那么旋转之后，旋转点左右的两部分仍然是递增的这里记原始数组中旋转点左侧的数组为 A，原始数组中旋转点右侧的数组为 B旋转之后有原来的 AB 变成了 BA

算法流程：

• 初始化： 声明 l, r双指针分别指向 nums 数组左右两端；
• 循环二分
• 返回值： 当 l = r 时跳出二分循环，并返回 旋转点的值 nums[l] 即可。

class Solution:    def minArray(self, numbers: List[int]) -> int:        l, r = 0, len(numbers) - 1        while l < r:            mid = (l + r) // 2            if numbers[mid] > numbers[r]:                # 说明mid在原来的 B 部分,l在mid基础上 往前一步                l = mid + 1            elif numbers[mid] < numbers[r]:                # 说明mid在A部分,mid做为新的终点r                r = mid            else:             	# 无法判断 mm 在哪个排序数组中,执行 r = r - 1j=j−1 缩小判断范围                r -= 1        return numbers[l]'''作者：LotusPanda链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/xiong-mao-shua-ti-python3-er-fen-fa-by-lotuspanda/来源：力扣（LeetCode）'''

当 numbers[mid] = numbers[r], 一定有区间 [l, m]内所有元素相等 或 区间 [m, r] 内所有元素相等（或两者皆满足）。对于寻找此类数组的最小值问题，可直接放弃二分查找，而使用线性查找替代。

即 else：	return min(numbers[i:j])

作者：Krahets

补充思考： 为什么本题二分法不用 nums[mid] 和 nums[l] 作比较？

• 二分目的是判断 m 在哪个排序数组中，从而缩小区间。而在 nums[mid] > nums[l] 情况下，无法判断 m 在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中； i 初始值无法确定在哪个排序数组中。举例如下：

  对于以下两示例，当 l = 0, r = 4, m = 2 时，有 nums[mid] > nums[l] ，而结果不同。

  [1, 2, 3, 4 ,5] 旋转点 x = 0 ： m 在右排序数组（此示例只有右排序数组）；
  [3, 4, 5, 1 ,2] 旋转点 x = 3 ： m 在左排序数组。

  链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5055b1/