- 本题难度: Medium
Topic: Binary Search
类似Description
- Search in Rotated Sorted Array II Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true Example 2:Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false Follow up:This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?我的的代码
class Solution: def search(self, A: 'List[int]', target: 'int') -> 'bool': # write your code here if A == []: return False l = 0 r = len(A)-1#注意！ f = -1 # breakpoint if len(A) == 1: return A[0] == target for i in range(1,len(A)): if A[i-1]>A[i]: f = i if f == -1: l = 0 r = len(A) - 1 else: if target>=A[0]: l = 0 r = f-1 else: l = f r = len(A)-1 while(l<=r): m = (l+r)//2 if A[m] == target: return True else: if A[m]>target: r = m-1 else: l = m+1 return False
思路
如果遇到[2,2,2,2,0,2,2]这类情况，没想好怎么做，所以
- 时间复杂度: O(log(n))
别人的代码
def search(self, nums, target): l, r = 0, len(nums)-1 while l <= r: mid = l + (r-l)//2 if nums[mid] == target: return True while l < mid and nums[l] == nums[mid]: # tricky part l += 1 # the first half is ordered if nums[l] <= nums[mid]: # target is in the first half if nums[l] <= target < nums[mid]: r = mid - 1 else: l = mid + 1 # the second half is ordered else: # target is in the second half if nums[mid] < target <= nums[r]: l = mid + 1 else: r = mid - 1 return False
思路
如果遇到[2,2,2,2,0,2,2]这类情况，没想好怎么做，所以
- 时间复杂度: average : O(log(n)) worst O(n)