本文共 1060 字，大约阅读时间需要 3 分钟。

JZ6 旋转数组最小数问题

题目链接

该题目来源于著名的算法面试题，题目描述如下：给定一个旋转排序数组，找出其中最小的数。数组的特点是其是排序数组的一次旋转，例如：[456, 123]，其中123是旋转后的有序部分。

本题思路

本题的解决思路利用了二分查找算法，通过对数组进行高效的查找，找到旋转后的最小数。以下是具体的实现步骤：

基本思路

二分查找逻辑

在二分查找过程中，主要比较两部分的值：

• 如果当前mid点的值小于等于hi点的值，说明最小数在lo到mid区间。
• 否则，最小数在mid到hi区间。

5. 返回结果：当lo和hi指针相邻时，返回较大的那个数。

代码实现

public class Solution {    public int minNumberInRotateArray(int[] array) {        if (array.length == 0) {            return 0;        }        int lo = 0;        int hi = array.length - 1;        while (lo <= hi) {            int mid = (lo + hi) / 2;            if (hi - lo == 1) {                return array[hi];            }            if (array[mid] <= array[hi]) {                hi = mid;            } else {                lo = mid;            }        }        return 0;    }}

代码解释

6. 特殊情况处理：首先检查数组是否为空，若为空返回0。
7. 初始化指针：lo设为0，hi设为数组末尾索引。
8. 二分查找循环：
   • 计算mid点。
   • 如果hi和lo相邻，直接返回hi点的值。
   • 比较mid点与hi点的值，决定调整hi或lo的位置。
9. 返回结果：循环结束后返回最小数。

该算法的时间复杂度为O(n)，能够在O(log n)时间内完成查找任务，效率非常高。