题目描述
统计一个数字在排序数组中出现的次数。
题目地址
思路
使用二分搜索,当搜索到与关键字相等时,在上下限之间遍历,计数。没找到则返回0
Python
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if not data:
return 0
l, r = 0, len(data)-1
while l<= r:
mid = (l+r)//2
if data[mid] == k:
count = 0
for i in range(l,r+1):
if data[i] == k:
count += 1
return count
elif data[mid] > k:
r = mid - 1
else:
l = mid + 1
return 0