原题地址：https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
题意：
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
解题思路：还是二分查找的变种。需要考虑好边界情况。
代码：
class Solution:
# @param A a list of integers
# @param target an integer
# @return a boolean
def search(self, A, target):
left=0; right=len(A)-1
while left<=right:
mid=(left+right)/2
if A[mid]==target: return True
if A[left]==A[mid]==A[right]:
left+=1; right-=1
elif A[left]<=A[mid]:
if A[left]<=target<A[mid]: right=mid-1
else: left=mid+1
else:
if A[mid]<=target<A[left]: left=mid+1
else:right=mid-1
return False