Question: http://oj.leetcode.com/problems/search-for-a-range/
Question Name: Search for a Range
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 | class Solution: # @param A, a list of integers # @param target, an integer to be searched # @return a list of length 2, [index1, index2] def searchRange(self, A, target): ''' Use binary search to find the occurrence range of target in array A. ''' begin = -1 end = -1 # Find the first occurrence of target in A front = len(A) - 1 back = 0 while back <= front: mid = (front + back) // 2 if A[mid] > target: front = mid - 1 elif A[mid] < target: back = mid + 1 else: front = mid - 1 begin = mid # Target is not found in the array A if begin == -1: return [-1, -1] # Find the last occurrence of target in A front = len(A) - 1 back = 0 while back <= front: mid = (front + back) // 2 if A[mid] > target: front = mid - 1 elif A[mid] < target: back = mid + 1 else: back = mid + 1 end = mid return [begin, end] |