Leetcode33.旋转排序数组与面试题11.旋转数组的最小数字 Python实现及其详解

本题要点就是：只在有上升顺序的那一端做二分查找，妥妥的能解决，并且思路清晰，虽然思路很简单，但是二分查找看的是细节，判断语句中使用大于等于，还是大于，或者使用小于等于还是小于，这些写错一个就可能会要了你的命！
代码实现：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
    	n = len(nums)
    	left,right =0,n-1
    	while left<=right:
    		mid = left+(right-left)//2
    		if nums[mid]==target:
    			return mid 
    		elif nums[left]<=nums[mid]:
    			if nums[left]<=target<nums[mid]:
    				right=mid-1
    			else:
    				left = mid+1
    		else:
    			if nums[mid]<taregt<=nums[right]:
    				left = mid+1
    			else:
    				right=mid- 1
    	return -1

自己每个一段时间做这道题的时候经常有以下几个地方会写错，经过这次整理之后希望以后不会写错了

1. 为什么是 while left <= right:, 在与正常的二分查找模板一样，我们要考虑当left和right相遇时，此时对应的值是否是target，所以不能把这个数给刨除掉
2. 为什么是 nums[left]<=nums[mid],这里我们考虑一个例子[2,1],target=1,此时对于这种情况，mid=0，如果是nums[left]
3. 为什么是nums[mid]

这道题的思路就是：使用mid值和right比较，这一点相当重要了

class Solution:
    def minArray(self, numbers: List[int]) -> int:
    	n = len(numbers)
    	left, right = 0,n-1
    	while left<right:
    		mid = left+(right-left)//2
    		if numbers[mid]<numbers[right]:
    			# 右侧递增,但是mid处可能是最小值
    			right=mid
    		elif numbers[mid]==numbers[right]:
    			# 就算right是最小值，把它过滤掉还有mid呢
    			right-=1
    		else:
    			# 左侧递增，那么mid肯定不是最小值
    			left = mid+1
    	return numbers[left]

同样的列举几个疑问你要是全理解了，估计这道题你就彻底懂了

1. 为什么while left
2. 为什么numbers[mid]>numbers[right]，要right=mid，因为我们只能得到mid的右侧包括mid在内组成的是一个递增数列，然而并不能确定mid处是否是一个最小值，即mid处可能是一个最小值
3. 为什么要left = mid+1？因为走到这一步可以明确，mid左侧，包括mid处是一个递增数列，那么递增的数列不可能存在最小值，那么可以执行left = mid+1