二分查找

寻找旋转排序数组中的最小值

中等#153Java时间 O(log n)空间 O(1)

题目要做什么

严格升序数组经过旋转,元素互不相同。用 O(log n) 时间找到最小值。

题目示例输入nums = [3,4,5,1,2]
题目示例输出1

01 为什么这样做

比较中间值和右端点。中间值更大时,最小值在右半段;否则最小值可能就是 mid,保留 mid 并缩小右边界。

始终成立的条件

最小值始终在闭区间 [left, right] 内。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int findMin(int[] nums) {3        int left = 0, right = nums.length - 1;4        while (left < right) {5            int mid = left + (right - left) / 2;6            if (nums[mid] > nums[right]) left = mid + 1;7            else right = mid;8        }9        return nums[left];10    }11}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索