求解旋转数组的最小数字

对于旋转数组的最小数字问题，有以下几个步骤：

1. 理解问题：旋转数组是将一个有序数组的最开始若干个元素搬到数组的末尾，形成一个新的数组的过程。问题即为在这个旋转后的数组中寻找最小值。

2. 思考解法：由于数组是旋转后的有序数组，我们需要利用这个性质来解决这个问题。可以采用以下三种解法：

3. 二分查找：将数组分为两部分，其中一部分一定是有序的。根据二分查找的思想，在有序部分查找最小值，若没找到，则在无序部分查找。时间复杂度为O(log n)

4. 线性查找：从头到尾遍历数组，找到一个数比前一个数小，则说明该数为最小值。时间复杂度为O(n)

5. 递归查找：由于旋转数组本质上仍然为有序数组，可以通过递归的方式寻找最小值。时间复杂度为O(n)，但空间复杂度较高。

6. 代码实现：

7. 二分查找的代码实现

python
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid
return nums[l]

• 线性查找的代码实现

python
class Solution:
def findMin(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i] < nums[i-1]:
return nums[i]
return nums[0]

• 递归查找的代码实现

python
class Solution:
def findMin(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if nums[0] < nums[-1]:
return nums[0]
mid = len(nums) // 2
if nums[mid] > nums[-1]:
return self.findMin(nums[mid+1:])
else:
return self.findMin(nums[:mid+1])

1. 示例说明：

2. 示例一：

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

   输出：0

   解释：经过旋转后，数组变为[0,1,2,4,5,6,7]，0为最小值。

3. 示例二：

   输入：[3,4,5,1,2]

   输出：1

   解释：经过旋转后，数组变为[1,2,3,4,5]，1为最小值。