153. 寻找旋转排序数组中的最小值
1. 题目描述
题目中转：153. 寻找旋转排序数组中的最小值
2.详细题解
如果不考虑
O
(
l
o
g
n
)
O(log n)
O(logn)的时间复杂度，直接
O
(
n
)
O(n)
O(n)时间复杂度的扫描遍历一次即可。
严格升序数组，即不存在相同元素的两个值。如果不旋转则最小的数值即为第一个（索引为0）的数值，数组旋转了1到n次，寻找数组中最小的元素，这道题是二分查找的变型题。
假定最小值为
m
i
n
x
min_x
minx，数组旋转后，假定结尾最后一个值为
t
a
i
l
tail
tail，对于最小值
m
i
n
x
min_x
minx，其右边的元素均小于
t
a
i
l
tail
tail，而其左边的元素均大于
t
a
i
l
tail
tail的值，可以利用该性质使用二分查找算法。
具体算法如下：
- Step1：初始化：两个指针 l e f t left left 和 r i g h t right right，分别指向数组的起始和结束位置；
- Step2：计算中间元素的索引： m i d = ( l e f t + r i g h t ) / 2 mid = (left + right) / 2 mid=(left+right)/2；
- Step3：如果 n u m s [ m i d ] < n u m s [ r i g h t ] nums[mid] < nums[right] nums[mid]<nums[right]，说明区间 ( m i d , r i g h t ] (mid, right] (mid,right]均为最小值右边的元素，故移除，更新 r i g h t = m i d right=mid right=mid，而 m i d mid mid可能为最小值，因此更新区间时不能舍弃 m i d mid mid；
- Step4：否则（即 n u m s [ m i d ] > = n u m s [ r i g h t ] nums[mid]>=nums[right] nums[mid]>=nums[right]），说明区间 [ l e f t , m i d ] [left,mid] [left,mid]均为最小值左边的元素，故移除，更新 l e f t = m i d + 1 left=mid+1 left=mid+1，此时 m i d mid mid值不可能为最小值，因为其已经大于了结尾值，故可舍弃 m i d mid mid;
- Step5：当指针left小于right时，重复步骤Step2_Step5；
- Step6：否则循环结束，返回 n u m s [ l e f t ] nums[left] nums[left]。
3.代码实现
3.1 Python
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[right]:
right = mid
else:
left = mid + 1
return nums[left]
3.2 Java
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left <right){
int mid = (left + right) / 2;
if (nums[mid] < nums[right]){right = mid;}
else{left = mid + 1;}
}
return nums[left];
}
}
执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code。
标签：153,right,nums,mid,最小值,tail,排序,left From： https://blog.csdn.net/weixin_38979465/article/details/140137381