题目描述

给定一个按升序排列的数组在一个未知的点上进行了旋转，例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。请编写一个函数找到旋转排序数组中的最小值。你可以假设数组中不存在重复元素。

解题思路

由于数组是部分有序的，我们可以利用二分查找的思想来加速查找过程。在每一步中，我们比较数组中间的元素与右边界的元素，根据它们的大小关系来缩小搜索范围。

1. 如果中间元素大于右边界元素，说明最小值一定在右半部分（不包括中间元素），因为左半部分是有序且都比右边界元素大的。
2. 如果中间元素小于或等于右边界元素，说明最小值要么在中间元素的左侧（包括中间元素），要么就是中间元素本身，因为右半部分（不包括中间元素）是有序且都比中间元素大的。

示例代码

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

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

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是数组的长度。