这个题中,可以用O(n)的时间复杂度遍历一遍数组,实现寻求数组中的最小值,但是没有利用旋转数组的性质。
运用旋转数组的性质,整体来看,旋转数组基本是保持有序性的,最小值将这个一维数组分成了两个。
运用二分搜索的方法,开始将两个指针分别放在两侧,求中间值,假设中间值大于等于左侧指针的数值,则中间值还将在左侧的那个数组,否则,中间值就在右侧的二维数组,此时依据情况更新两个指针,便可缩小范围,最后结束循环的条件为r - l == 1为退出循环条件。
最终l指针将指向第一个数组的最右边,r将指向第二个数组的最左边,直接返回r即为结果。
在以上基础上,循环括号内的条件可以为l<=r。
但是这样不严谨,假设该数组旋转了0个元素,此时最左边的元素就是最小值,如果还是按照上述方法,就会跳过去,此时将while循环条件改为nums[l]>=nums[r],因为根据题意,数组为旋转数组,现在左边第一个元素值肯定要大于等于现在数组中的最后一个元素值的。
此时将mid初始化为l,当循环内部r - l == 1时,将mid = r,返回r。此时若旋转0个时,也直接返回mid即第一个元素。
此时还有针对特殊情况的分析,假设数组为[1,1,1,0,1]当遇到第一个数组时,该如何分析呢,无法正确定位到最小值在哪个元素中。此时应该当判断到中间节点nums[mid] == nums[l] == nums[r]时,此时应当从当前l-r顺序遍历一遍数组,求最小值。
详细看剑指offer课本。
自己好菜。