此题应该是leetcode最让人无语的题之一 表面上是考二分法 实际上是考察代码的鲁棒性（说人话，就是各种特殊情况、边界情况） 我们首先看看数组是否发生翻折(也就是说，会不会凑巧在[0]位置发生翻折，导致和没翻一样) 怎么看呢？ 只需要比较nums[0]和nums[-1]即可 则 有三种可能 1、nums[0] > nums[-1] 此时即为没翻折，全区域有序 普通二分即可 2、nums[0] == nums[-1] 最sb的情况， 如数组是[2,1,2,2,2],问你1是否存在？ 如数组是[2,2,2,2,2],也让你找1 对于这种情况，可以先判断一样的元素是不是target 不是的话 用递归同时消去两边一样的元素， 即return self.search(nums[1:-1],target) 直到首尾不一样，此时最好再检查以下首尾有无target 然后再按下面的“3、”操作 3、nums[0] >= nums[-1] 此时为最一般的情况，找翻折轴 因为有相等的元素，找翻折轴的时候也需要注意相等 找到后，先看看翻折轴是不是target 如果不是，再根据局部有序，判断target在哪半边，二分即可
class Solution: def search(self, nums, target): length = len(nums) if length <= 5: return True if target in nums else False if nums[0] == target or nums[-1] == target: return True if nums[0] == nums[-1]:#fuck you return self.search(nums[1:-1],target) if nums[0] < nums[-1]: start = 0 end = length - 1 else: axis = self.findaxis(nums,0,length - 1) print('axis,',axis) if target == nums[0] or target == nums[-1] or target == nums[axis] or (axis + 1 <= length - 1 and target == nums[axis + 1]): return True else: (start,end) = (0,axis) if target > nums[0] else (axis+1,length-1) while start < end: if target == nums[start] or target == nums[end]: return True elif start == end + 1 and target not in [arr[start],arr[end]]: return False mid = start + ((end-start)>>1) if target == nums[mid]: return True elif target < nums[mid]: end = mid - 1 elif target > nums[mid]: start = mid + 1 return False def findaxis(self,arr,i,j): mid = i + ((j-i)>>1) print(i,j,mid) if i >= j - 1: return i if arr[i] > arr[j] else j if arr[mid] >= max(arr[i],arr[j]) and arr[mid] > arr[mid + 1]:#找到了翻折轴 return mid elif arr[mid] > max(arr[i],arr[j]): return self.findaxis(arr,mid+1,j) elif arr[mid] <= min(arr[i],arr[j]): return self.findaxis(arr,i,mid-1) else: return j