题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2] 输出: 1

示例 2:

输入: [4,5,6,7,0,1,2] 输出: 0

解题思路：

这个问题可以通过二分查找来解决。由于数组是旋转过的有序数组，我们可以利用二分查找的特性来找到最小值。

1. 初始化：设置两个指针 left 和 right，分别指向数组的起始和末尾位置。
2. 二分查找：
   • 计算中间位置 mid。
   • 比较 mid 位置的值与 right 位置的值：
     • 如果 nums[mid] > nums[right]，说明最小值在 mid 的右侧，调整 left 为 mid + 1。
     • 否则，说明最小值在 mid 的左侧或者就是 mid，调整 right 为 mid。
3. 终止条件：当 left 和 right 相等时，left（或 right）指向的就是最小值。

代码实现：

def findMin(nums): left, right = 0, len(nums) - 1

while left < right:
    mid = (left + right) // 2

    if nums[mid] > nums[right]:
        left = mid + 1
    else:
        right = mid

return nums[left]

print(findMin([3,4,5,1,2])) # 输出: 1 print(findMin([4,5,6,7,0,1,2])) # 输出: 0

详细解释：

1. 初始化：
   • left = 0，right = len(nums) - 1。
2. 二分查找过程：
   • 计算中间位置 mid。
   • 比较 nums[mid] 和 nums[right]：
     • 如果 nums[mid] > nums[right]，说明最小值在 mid 的右侧，调整 left 为 mid + 1。
     • 否则，说明最小值在 mid 的左侧或者就是 mid，调整 right 为 mid。
3. 终止条件：
   • 当 left 和 right 相等时，循环结束，此时 left（或 right）指向的就是最小值。

复杂度分析：

• 时间复杂度：O(log n)，二分查找的时间复杂度为对数级别。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

通过这种方法，我们可以在对数时间内高效地找到旋转有序数组中的最小值。