153and154、|153and154、查找旋转有序数组中的最小值 153and154、查找旋转有序数组中

文章图片
一、解题思路： 1、如果直接用遍历，数组在一定意义上是有序的，所以一开始就直接遍历不是最好的选择，考虑用二分法将复杂度降为O(logn)
2、用二分查找，就涉及到left，right，mid之间的操作了。这时候，就多写出几个不同的例子，分一下情况，尤其重要的是，一定要把下一次循环的指针赋值写对了。
为此，在写完代码以后要自己测试一下。
3、从一般到特殊——功能测试
根据写出来的几个一般的例子，我们可以认为，最左边的元素一定大于最右边的元素。
二、代码思路每次循环时，因为left或right也在变，因此mid也要改变：mid等于left+right的和再整除2，注意除号是反斜杠。
循环中操作
选择中间item进行下一步的比较操作

若中间元素大于最左边的元素，那么说明左半部分都是比较大的元素，
最小的元素在右半部分,因此应该把mid赋值给left，下次在新的left到right区间进行查找。
同理于中间元素小于最右边元素的情况。

循环终止条件

设置左右指针left与right，根据上述两种情况，编写循环
考虑最后边界的情况，当左右指针靠近（右指针比左指针大1）的时候
因为右边才是最小部分，所以最小值就在右边

三、代码测试功能测试（数组中不含相同元素）：

输入一般的旋转排序数组
输入旋转0个元素的数组（也就是未旋转的数组）
此时我们发现再去比较中间的并不适用了，可以直接返回数组的第一个元素。

边界测试：

数组为空
数组只含一个

特殊情况数组
若是mid，left，right三个位置的元素都相等，那我们没有办法确定最小元素在哪一半。此时，只能采取顺序查找了。因此，可以专门写一个顺序查找的函数。
【153and154、|153and154、查找旋转有序数组中的最小值】代码实现：

class Solution: def findMin(self, nums): """ :type nums: List[int] :rtype: int """# 定义一个顺序查找的函数 def minOrder(nums): min_num = nums[0] for i in nums: if i < min_num: min_num = i return min_numif nums: if len(nums) == 1: return nums[0] left = 0 right = len(nums) - 1 #除号是反斜杠，一定要注意 mid = len(nums) // 2 #没有元素旋转的情况 if nums[right] > nums[left]: return nums[0] #三个指针元素都相等的情况 if nums[mid] == nums[left] and nums[mid] == nums[right]: minOrder(nums)#一般情况 while right - left > 1: mid = (right + left) // 2 if nums[mid] > nums[left]: print(nums[mid:right+1]) left = mid else: print(nums[left:mid]) right = mid return nums[right] else: return NoneSolution = Solution() print(Solution.findMin([0,1,2,4,5,6,7,8,9,10]))