38-数字在排序数组中出现的次数

暴力法，也没用到排序

创建一个字典，记录每个数的出现次数，之后返回就可以了。

def GetNumberOfK(self, data, k):
    # write code here
    d = dict()
    for i in data:
        if i not in d:
            d[i] =1
        else:
            d[i] +=1
    if k not in d:
        return 0
    return d[k]

二分法，因为是排序的数字，所以二分法是一个比较好的选择。

使用二分法找到对应的数，然后向前判断前面的数是否为相等的数，向后判断也一样，之后返回。

def GetNumberOfK(self, data, k):
    # write code here
    if not data:
        return 0
    count = 0
    l =0
    r = len(data)-1
    mid =  (l+r)//2
    while l<=r:
        if data[mid]>k:
            r = mid
            mid = (r+l)//2
        if data[mid]<k:
            l = mid
            mid = (r+l)//2
        if data[mid]==k:
            p = mid
            while p>=0 and data[p]==k :
                count +=1
                p -=1
            p = mid
            while p< len(data) and data[p]==k :
                count +=1
                p+=1
            return count-1
        return count