第一種做法
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if len(nums) == 0:
return False
if len(nums) == 1 and target != nums[0]:
return False
if len(nums) == 1 and target == nums[0]:
return True
q = 0
for i in range(len(nums)):
if i > 0 and nums[i] < nums[i-1]:
q = i
break
if q == 0:
return self.half(nums, target)
elif target >= nums[0]:
return self.half(nums[:q], target)
else:
return self.half(nums[q:], target)
def half(self, nums, target):
l = 0
r = len(nums) - 1
while l <= r:
m = (l + r)/2
if nums[m] == target:
return True
elif nums[m] > target:
r = m -1
else:
l = m + 1
return False
這一題和Ⅰ一樣炸卑，因此第二種方法
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if len(nums) == 0:
return False
if len(nums) == 1 and target != nums[0]:
return False
if len(nums) == 1 and target == nums[0]:
return True
l = 0
r = len(nums) - 1
while l <= r:
m = (l + r) / 2
if nums[m] == target:
return True
if nums[m] > nums[l]:
if nums[l] <= target <= nums[m]:
r = m - 1
else:
l = m + 1
elif nums[m] < nums[l]:
if nums[m] <= target <= nums[r]:
l = m + 1
else:
r = m - 1
else:
l += 1
return False
