数据结构与算法之 leetcode 二分查找旋转数组 查找最小值

二分查找旋转数组：寻找最小值

在处理数组问题时，二分查找算法是一个高效且常用的方法。当数组经过旋转操作后，传统的二分查找方法就不再适用。本文将围绕“二分查找旋转数组：寻找最小值”这一主题，深入探讨如何利用二分查找算法在旋转数组中找到最小值。

旋转数组是指将一个有序数组中的元素按照某个数k（k <= 数组长度）进行旋转，使得数组变为一个新数组。例如，一个有序数组 `[1, 2, 3, 4, 5, 6, 7]` 经过旋转 `3` 次后，变为 `[4, 5, 6, 7, 1, 2, 3]`。在旋转数组中查找最小值是一个经典的算法问题。

问题描述

给定一个旋转数组 `nums`，其中 `nums[i] >= nums[i+1]`（除了最后一个元素），找出并返回数组中的最小值。

解题思路

要解决这个问题，我们可以利用二分查找算法。由于数组是旋转的，我们可以将问题转化为在有序数组中查找最小值。以下是解题步骤：

1. 初始化两个指针 `left` 和 `right`，分别指向数组的第一个和最后一个元素。

2. 当 `left` 小于 `right` 时，执行以下操作：

a. 计算中间位置 `mid`。

b. 如果 `nums[mid]` 大于 `nums[right]`，则最小值在 `mid` 的右侧，将 `left` 更新为 `mid + 1`。

c. 否则，最小值在 `mid` 的左侧或 `mid` 本身，将 `right` 更新为 `mid`。

3. 当 `left` 等于 `right` 时，返回 `nums[left]` 即为最小值。

代码实现

下面是使用 Python 实现的代码：

python
def findMin(nums):

    left, right = 0, len(nums) - 1

    while left < right:

        mid = (left + right) // 2

        if nums[mid] > nums[right]:

            left = mid + 1

        else:

            right = mid

    return nums[left]

 测试代码

nums = [4, 5, 6, 7, 1, 2, 3]

print(findMin(nums))   输出：1

时间复杂度和空间复杂度

该算法的时间复杂度为 O(log n)，空间复杂度为 O(1)。这是因为我们使用了二分查找算法，每次迭代都将搜索范围缩小一半。

总结

本文介绍了如何在旋转数组中查找最小值。通过分析旋转数组的特性，我们利用二分查找算法实现了高效查找。在实际应用中，我们可以根据具体问题选择合适的算法，以提高代码的执行效率。