题目链接
难度：中等 类型：数组、二分搜索
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例1
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例2
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
解题思路
二分搜索：
若nums[left]==nums[right]==nums[mid]，是无法二分的，只能遍历
否则就可以二分，移动有指针的情况有：
nums[mid]>target>nums[left] or nums[mid]<nums[left]<target or target< nums[mid]<nums[left]
其余情况移动左指针
代码实现
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if not nums:
return False
left, right = 0, len(nums)-1
while left<right:
mid = (left+right)//2
if nums[left] == nums[right] == nums[mid]:
while left<right:
if nums[left] == target:
return True
left += 1
return False
if nums[mid] == target or nums[left]==target:
return True
elif nums[mid]>target>nums[left] or nums[mid]<nums[left]<target or target< nums[mid]<nums[left]:
right = mid
else:
left = mid + 1
return True if nums[left]==target else False
