Question: https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
Question Name: Search in Rotated Sorted Array II
I did not notice, there is no duplicate in Search in Rotated Sorted Array. SO I’ve done this in that question.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Solution: # @param A, a list of integers # @param target, an integer to be searched # @return an integer def _searchHelper(self, A, target, begin, end): if begin > end: return -1 mid = (begin + end) // 2 if A[begin] < A[end]: rotated = False else: rotated = True if A[mid] == target: return mid elif A[mid] < target: if rotated: temp = self._searchHelper(A, target, begin, mid - 1) if temp != -1: return temp return self._searchHelper(A, target, mid + 1, end) else: if rotated: temp = self._searchHelper(A, target, mid + 1, end) if temp != -1: return temp return self._searchHelper(A, target, begin, mid - 1) # @param A, a list of integers # @param target, an integer to be searched # @return a boolean def search(self, A, target): if self._searchHelper(A, target, 0, len(A)-1) == -1: return False else: return True |