当前位置： 面试刷题>> 寻找旋转排序数组中的最小值(经典算法150题)
### 题目描述
给定一个按升序排列的数组在一个未知的点上进行了旋转，例如，数组 `[0,1,2,4,5,6,7]` 可能变为 `[4,5,6,7,0,1,2]`。请编写一个函数找到旋转排序数组中的最小值。你可以假设数组中不存在重复元素。
### 解题思路
由于数组是部分有序的，我们可以利用二分查找的思想来加速查找过程。在每一步中，我们比较数组中间的元素与右边界的元素，根据它们的大小关系来缩小搜索范围。
1. 如果中间元素大于右边界元素，说明最小值一定在右半部分（不包括中间元素），因为左半部分是有序且都比右边界元素大的。
2. 如果中间元素小于或等于右边界元素，说明最小值要么在中间元素的左侧（包括中间元素），要么就是中间元素本身，因为右半部分（不包括中间元素）是有序且都比中间元素大的。
### 示例代码
#### PHP
```php
function findMin(array $nums): int {
$left = 0;
$right = count($nums) - 1;
while ($left < $right) {
$mid = $left + floor(($right - $left) / 2);
if ($nums[$mid] > $nums[$right]) {
// 最小值在右半部分
$left = $mid + 1;
} else {
// 最小值在左半部分或就是中间元素
$right = $mid;
}
}
return $nums[$left];
}
// 示例
$nums = [4,5,6,7,0,1,2];
echo findMin($nums); // 输出: 0
```
#### Python
```python
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# 最小值在右半部分
left = mid + 1
else:
# 最小值在左半部分或就是中间元素
right = mid
return nums[left]
# 示例
nums = [4,5,6,7,0,1,2]
print(findMin(nums)) # 输出: 0
```
#### JavaScript
```javascript
function findMin(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) {
// 最小值在右半部分
left = mid + 1;
} else {
// 最小值在左半部分或就是中间元素
right = mid;
}
}
return nums[left];
}
// 示例
const nums = [4,5,6,7,0,1,2];
console.log(findMin(nums)); // 输出: 0
```
通过这些示例代码，你可以看到如何在PHP、Python和JavaScript中利用二分查找算法来解决寻找旋转排序数组中的最小值的问题。这种解法的时间复杂度为O(log n)，其中n是数组的长度。