0153. 寻找旋转排序数组中的最小值 #
- 标签:数组、二分查找
- 难度:中等
题目大意 #
给定一个数组 nums
,nums
是有升序数组经过「旋转」得到的。但是旋转次数未知。数组中不存在重复元素。
要求:找出数组中的最小元素。
- 旋转:将数组整体右移。
解题思路 #
数组经过「旋转」之后,会有两种情况,第一种就是原先的升序序列,另一种是两段升序的序列。
第一种的最小值在最左边。第二种最小值在第二段升序序列的第一个元素。
|
|
|
|
最直接的办法就是遍历一遍,找到最小值。但是还可以有更好的方法。考虑用二分查找来降低算法的时间复杂度。
创建两个指针 left
、right
,分别指向数组首尾。让后计算出两个指针中间值 mid
。将 mid
与两个指针做比较。
- 如果
nums[mid] > nums[right]
,则最小值不可能在mid
左侧,一定在mid
右侧,则将left
移动到mid + 1
位置,继续查找右侧区间。 - 如果
nums[mid] ≤ nums[right]
,则最小值一定在mid
左侧,或者mid
位置,将right
移动到mid
位置上,继续查找左侧区间。
代码 #
|
|