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) 的算法解决此问题。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

void printArray(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

/*
    二分查找

    假设数组中的最后一个元素 x：
        在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；
        在最小值左侧的元素，它们的值一定都严格大于 x。
    根据这一条性质，二分找出最小值。

    在二分查找的每一步，左边界为 l，右边界为 r，区间的中点为 mid，最小值就在该区间内。
    将中轴元素 nums[mid] 与右边界元素 nums[r] 进行比较，可能的情况如下：
        nums[mid] < nums[r]
            这说明 nums[mid] 是最小值右侧的元素，可以忽略二分查找区间的右半部分。
        nums[mid] > nums[r]
            这说明 nums[mid] 是最小值左侧的元素，可以忽略二分查找区间的左半部分。
    注意：处理特殊情况，数组完全单调。

    时间复杂度：O(logn)
        其中 n 是数组 nums 的长度。
        在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为 O(logn)。
    空间复杂度：O(1)
*/
class Solution_0 {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;
        // 处理特殊情况：数组完全单调
        if (nums[n] >= nums[0]) return nums[0];

        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            // 判断 nums[0]，不是 nums[l]
            if (nums[mid] < nums[0]) r = mid; // 左边乱序，向左走
            else l = mid + 1;                 // 右边乱序，向右走
        }

        return nums[r]; // 结束条件：l == r
    }
};

/*
    思路同上
*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        // 处理特殊情况：数组完全单调
        if (nums[nums.size() - 1] >= nums[0]) return nums[0];

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            // if (nums[mid] < nums[r]) r = mid;
            // else l = mid + 1;
            if (nums[mid] < nums[r]) r = mid;
            else if (nums[mid] > nums[r]) l = mid + 1;
            else if (nums[mid] == nums[r]) l = mid + 1;
        }

        return nums[r];
    }
};

int main() {
    Solution solution;
    vector<int> nums = {3, 4, 5, 1, 2};
    printArray(nums);
    int result = solution.findMin(nums);
    cout << "The minimum value in the array is: " << result << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   旋转排序数组的特点是：
       数组被分为两部分，其中一部分是有序的。
       最小值位于旋转点处，即数组的“断点”。
       利用这一特性，可以通过二分查找高效地找到最小值。

   时间复杂度：O(logn)
       二分查找：每次迭代将搜索范围缩小一半，因此时间复杂度为 O(logn)，其中 n 是数组的长度。
   空间复杂度：O(1)
       常数空间：仅使用了两个指针 left 和 right，空间复杂度为 O(1)。
*/
// findMin 在旋转排序数组中找到最小值
func findMin(nums []int) int {
	left, right := 0, len(nums) - 1

	for left < right {
		mid := left + (right - left )/ 2
		if nums[mid] > nums[right] {
			// 最小值在 mid 的右侧
			left = mid + 1
		} else {
			// 最小值在 mid 的左侧或就是 mid
			right = mid
		}
	}

	return nums[left]
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected int
	}{
		{[]int{3, 4, 5, 1, 2}, 1},
		{[]int{4, 5, 6, 7, 0, 1, 2}, 0},
		{[]int{11, 13, 15, 17}, 11},
	}

	for i, tc := range testCases {
		result := findMin(tc.nums)
		fmt.Printf("Test Case %d: Input: nums = %v\n", i+1, tc.nums)

		if result == tc.expected {
			fmt.Printf("Output: %d, PASS\n", result)
		} else {
			fmt.Printf("Output: %d, FAIL (Expected: %d)\n", result, tc.expected)
		}
	}
}