【剑指offer】Q38:数字在数组中出现的次数

时间:2022-02-06 11:04:05

与折半查找是同一个模式,不同的是,在这里不在查找某个确定的值,而是查找确定值所在的上下边界。

def getBounder(data, k, start, end, low_bound = False):
if end < start : return -1

while start <= end:
mid = ( start + end ) >> 1
if data[ mid ] > k:
end = mid - 1
elif data[ mid ] < k:
start = mid + 1
else:
if low_bound == True:
if mid == 0 or data[ mid - 1 ] != k:
return mid
else:
end = mid - 1
else:
if mid == end or data[ mid + 1 ] != k:
return mid
else:
start = mid + 1

def getNumberOfk(data, k):
if len(data) <= 1: return len(data)
low_bound = getBounder( data, k, 0, len( data ) - 1, low_bound = True )
up_bound = getBounder( data, k, 0, len( data ) - 1, low_bound = False)
return up_bound - low_bound + 1