目录：

目的

思路

复杂度

记忆秘诀

python代码

目的：

旋转数组 [3,4,5,1,2] 的最小值是 1。

---

思路

这个任务是找到部分有序数组的最小值。你来到一家超市，这里的商品价格原本是按照顺序从便宜到贵摆放的，但有个手欠的人，把一部分商品挪到了前面，现在你想要找到最便宜的（最小值）。虽然顺序被打乱了，但你发现了超市的商品摆放仍然是部分有序的。你决定用二分查找法快速锁定价格最低的商品。

---

左手右手一个慢动作​​​​​：

• 左手：一开始放在第一个上（left = 0）。
• 右手：放在最后一个上（right = len(nums) - 1）。
• 用两只手的距离找到中间位置（mid）。从中间开始判断最便宜的商品在哪边。

---

右手左手慢动作重播：

• 如果中间价格比右手的贵：说明最便宜的商品在右边的范围内（右手指着的范围更便宜）。左手移动到 mid + 1，缩小范围。
• 如果中间价格比右手的便宜：说明最便宜的商品在左边的范围内（包含中间标签）。右手移动到 mid，缩小范围。
• 如果中间价格和右手价格一样：你无法确定最便宜的商品在哪边，只能让右手往左挪一格（缩小范围）。

---

给你快乐你有没有爱上我：当两只手指向同一个商品时，这一定是最便宜的！

---

复杂度

• 时间复杂度：O(log n）

  • 因为每次查找都将查找范围缩小一半。

• 空间复杂度：O(1)

  • 只使用了常数级别的额外空间。

---

记忆秘诀

• 左小右大分半查，最小藏在变乱家。
• 大往右移，小收左区，相等右退避。
• 左右合并不再差，结果就在左手下。

---

python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:def minNumberInRotateArray(self, nums: List[int]) -> int:if not nums:return 0  # 或者根据需要返回一个合适的值left, right = 0, len(nums) - 1while left < right:mid = left + (right - left) // 2# 如果中间元素大于右边元素，最小值在右边if nums[mid] > nums[right]:left = mid + 1# 如果中间元素小于右边元素，最小值在左边elif nums[mid] < nums[right]:right = midelse:right -= 1  # 当 nums[mid] == nums[right] 时，不能确定最小值的位置，缩小右边界return nums[left]

---

ps: python还有最简单的办法直接获得数组的最小值：（适合笔试）

return min(num)

* 欢迎大家探讨新思路，能够更好的理解和记忆