题目标题

给一个旋转有序的数组,所谓旋转有序,比如1,2,3,4,5算。4,5,6,1,2,3也算。在这个数组中查找元素p,返回bool是否找到。

参考解析
  1. class Solution:
  2. def search(self, nums, target):
  3. size = len(nums)
  4. if size == 0:
  5. return -1
  6. left = 0
  7. right = size - 1
  8. while left < right:
  9. #注意,这里选用的是左中位数
  10. mid = left + (right-left)//2
  11. #左半部分有序
  12. if nums[left] < nums[mid]:
  13. if nums[left] <= target <= nums[mid]:
  14. right = mid
  15. else:
  16. left = mid + 1
  17. #右半部分有序
  18. else:
  19. #为了使这里left和right的更新和上面一样,所以使用nums[mid+1]
  20. if nums[mid+1] <= target <= nums[right]:
  21. left = mid + 1
  22. else:
  23. right = mid
  24. # 后处理
  25. return left if nums[left] == target else -1