有序数组被旋转过后求最小点

Question

假设一个有序数组被旋转过 k 次，找到最小的元素。假设数组中不存在重复元素。

例如，旋转前的原始数组为 [1,2,3,4,5]，在索引 2 处（即数字 3）旋转数组以获得 [3,4,5,1,2]。该数组的最小值为 1。

解题思路

我们需要在旋转数组中搜索最小元素，可以使用二分搜索来解决问题。在典型的二分搜索中，我们在搜索空间中找到一个中间点并根据中间点比目标的大小关系将搜索空间缩小到左半部分或右半部分。

但是，本题中我们需要在旋转数组中搜索目标元素，因此我们需要一个变形的二分搜索来搜索最小元素。而这个变形的二分搜索可以通过比较中间元素和右侧元素来实现。

我们可以比较中间元素和最右侧元素，以确定最小元素位于左侧还是右侧。如果中间元素比最右侧元素大，则最小元素位于中间元素右侧。否则，最小元素位于中间元素左侧或者就是中间元素本身。因为最小元素不可能位于右侧，所以我们可以将右侧元素与中间元素进行比较。这样比较的结果告诉我们如果右侧元素比中间元素小，则最小元素位于右侧；否则，最小元素位于左侧。

在这样的二分搜索中，我们在搜索空间中选择中间点，并根据中间点与最右侧元素的比较来将搜索空间逐渐缩小为左侧或右侧。每次比较都可以减少搜索空间的一半。

代码实现

Java

public class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
}

Python

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

时间复杂度：O(logN)

空间复杂度：O(1)