# Share straight-forward 53 ms python solution, binary search

• ``````class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {integer[]}
def searchRange(self, nums, target):
return [self.utilSearchLeft(0, len(nums)-1, nums, target), self.utilSearchRight(0, len(nums)-1, nums, target)]

def utilSearchLeft(self, beg, end, arr, target):
# terminating condition, return index
if (end - beg + 1) == 1:
if arr[beg] == target:
return beg
else:
return -1

# binary breakdown with computing median
mid, med = self.utilGetMedian(beg, end, arr)

# odd number
if len(mid) == 1:
if med < target:
# search right half
if mid[0] < end:
return self.utilSearchLeft(mid[0]+1, end, arr, target)
else:
return -1
elif med > target:
# search left half
if mid[0] > beg:
return self.utilSearchLeft(beg, mid[0]-1, arr, target)
else:
return -1
else:
if mid[0] > beg:
# keep searching left excluding median
if self.utilSearchLeft(beg, mid[0]-1, arr, target) > -1:
return self.utilSearchLeft(beg, mid[0]-1, arr, target)
else:
return mid[0]
else:
return mid[0]

# even number
else:
if med < target:
# search right half
return self.utilSearchLeft(mid[1], end, arr, target)
elif med > target:
# search left half
return self.utilSearchLeft(beg, mid[0], arr, target)
else:
if (arr[mid[0]] != arr[mid[1]]):
# no such target exist
return -1
else:
if mid[0] > beg:
# keep search left excluding median
if self.utilSearchLeft(beg, mid[0]-1, arr, target) > -1:
return self.utilSearchLeft(beg, mid[0]-1, arr, target)
else:
return mid[0]
else:
return mid[0]

def utilSearchRight(self, beg, end, arr, target):

# terminating condition, return index
if (end - beg + 1) == 1:
if arr[beg] == target:
return beg
else:
return -1

# binary breakdown with computing median
mid, med = self.utilGetMedian(beg, end, arr)

# odd number
if len(mid) == 1:
if med < target:
# search right half
if mid[0] < end:
return self.utilSearchRight(mid[0]+1, end, arr, target)
else:
return -1
elif med > target:
# search left half
if mid[0] > beg:
return self.utilSearchRight(beg, mid[0]-1, arr, target)
else:
return -1
else:
if mid[0] < end:
# keep searching right excludind median
if self.utilSearchRight(mid[0]+1, end, arr, target) > -1:
return self.utilSearchRight(mid[0]+1, end, arr, target)
else:
return mid[0]
else:
return mid[0]

# even number
else:
if med < target:
# search right half
return self.utilSearchRight(mid[1], end, arr, target)
elif med > target:
# search left half
return self.utilSearchRight(beg, mid[0], arr, target)
else:
if (arr[mid[0]] != arr[mid[1]]):
return -1
else:
if mid[1] < end:
# keep search right excluding median
if self.utilSearchRight(mid[1]+1, end, arr, target) > -1:
return self.utilSearchRight(mid[1]+1, end, arr, target)
else:
return mid[1]
else:
return mid[1]

def utilGetMedian(self, beg, end, arr):
if (end-beg+1)%2 == 1:
return [(beg+end)/2], arr[(beg+end)/2]
else:
return [(beg+end)/2, (beg+end)/2+1], (arr[(beg+end)/2] + arr[(beg+end)/2+1])/2.0``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.