Question: http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
Question Name: Search in Rotated Sorted Array
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 30 31 32 33 34 35 36 37 38 39 | class Solution: # @param A, a list of integers # @param target, an integer to be searched # @param begin, an integer to indicate the begin pos to search # @param end, an integer to indicate the end pos to search # @return an integer def _searchHelper(self, A, target, begin, end): ''' Use a modified binary search algorithm to find the target in a may-be-rotated array A from position begin to end. ''' # Did not find the target if begin > end: return -1 mid = (begin + end) // 2 if A[begin] < A[end]: rotated = False # Sorted and not rotated else: rotated = True # Sorted and then rotated if A[mid] == target: # Target found return mid elif A[mid] < target: # If array is not rotated, no need to search in the left part if rotated: # Target might be in the left part temp = self._searchHelper(A, target, begin, mid - 1) if temp != -1: return temp # Search in the right part return self._searchHelper(A, target, mid + 1, end) else: # If array is not rotated, no need to search in the right part if rotated: # Target might be in the right part temp = self._searchHelper(A, target, mid + 1, end) if temp != -1: return temp # Search in the left part return self._searchHelper(A, target, begin, mid - 1) # @param A, a list of integers # @param target, an integer to be searched # @return an integer def search(self, A, target): return self._searchHelper(A, target, 0, len(A)-1) |