首页 > 代码库 > 【剑指offer】Q38:数字在数组中出现的次数

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

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

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