Leetcode153. 寻找旋转排序数组中的最小值（无重复元素）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

题解：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码如下：

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

题目要求实现O(logn)O(log_n)O(logn​) 的算法，这里使用二分查找以利用数组的部分有序性质，这里我们不需要找到特定的target元素，而是只需要找到最小值元素。实际上只要我们的算法是在每一步都缩小一半的搜索空间，那本质上就是在执行二分查找，只不过这里执行的二分查找相对于传统的二分查找做了特殊的边界处理：

1. 首先，我们定义两个指针 low 和 high，分别指向数组的开头和末尾。
2. 然后，我们进入一个 while 循环，只要 low 不等于 high，循环就会继续。
3. 在每次循环中，我们计算中间位置 pivot。我们将 nums[pivot]（即中间元素）与 nums[high]（即当前搜索空间的最后一个元素）进行比较。
   • 如果 nums[pivot] < nums[high]，这意味着从 pivot 到 high 的元素是有序的，因此最小值不可能在这个范围内，我们将 high 移动到 pivot，从而缩小搜索空间。
   • 否则，即 nums[pivot] >=nums[high]，这意味着最小值可能在 pivot 右侧，因此我们将 low 移动到 pivot + 1。
4. 当 low == high 时，搜索空间只剩一个元素，这就是我们要找的最小元素。 虽然整个数组不是完全有序的，但通过利用旋转数组的特性，我们仍然可以使用二分查找来找到最小的元素。

为什么将 high 移动到 pivot，而不是移动到pivot左侧？

这个问题的答案在于，pivot 可能就是最小的元素。 如果我们将 high 移动到 pivot 左侧（即 high = pivot - 1），那么我们就会错过检查 pivot 元素是不是最小元素的机会，因为下一次循环中，我们不会再考虑 pivot 元素。 我们正在寻找旋转排序数组中的最小元素。旋转排序数组的特性是，所有在旋转点后的元素都比旋转点前的元素小。这意味着，如果 nums[pivot] < nums[high]，那么 pivot 就有可能是最小元素，或者在其左侧。 因此，当 nums[pivot] < nums[high] 时，我们需要将 high 移动到 pivot，而不是 pivot - 1，以保证不会错过最小元素。

 

 二分查找：为什么左右不对称？只比较mid与right的原因（C++, Java, Python3）:

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台