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

题目描述
统计一个数字在排序数组中出现的次数。

思路：考查二分查找，递归法和循环法都要会。

def GetNumberOfK(self, data, k):
    # write code here
    # write code here
    # #有序数组就应该想到二分法，找到重复数字最左边和最右边的数字，然后两个相减就可以了
    num = 0
    if data:
        first = self.getFirstK(data, k , 0, len(data) - 1)
        last = self.getLastK(data, k, 0, len(data) - 1)
        if first > -1 and last > -1:
            num = last - first + 1
    return num
def getFirstK(self, data, k, start, end):
    if start > end:
        return -1
    mid = (start + end) / 2
    midD = data[mid]
    if midD > k:
        end = mid - 1
    elif midD < k:
        start = mid + 1
    else:
        #如果相等，mid为0，或者midD的前一个数不是k，那么此时的mid是最左边的k的编号
        if (mid == 0) or (mid > 0 and data[mid - 1] != k):
            return mid
        else:#如果相等，或者midD的前一个数是k，则end再向前移动一个单位
            end = mid - 1
    return self.getFirstK(data, k, start, end)
def getLastK(self, data, k, start, end):
    if start > end:
        return -1
    mid = (start + end) / 2
    midD = data[mid]
    if midD > k:
        end = mid - 1
    elif midD < k:
        start = mid + 1
    else:#如果相等，mid为最后一位，或者midD的后一个数不是k，那么此时的mid是最右边的k的编号
        if (mid == len(data) - 1) or (mid < len(data) - 1 and data[mid + 1] != k):
            return mid
        else:#如果相等，或者midD的后一个数是k，则start再向后移动一个单位
            start = mid + 1
    return self.getLastK(data, k, start, end)
#     #有序数组就应该想到二分法，找到重复数字最左边和最右边的数字，然后两个相减就可以了
#     left=0
#     right=len(data)-1
#     leftk=self.getleftK(data,k,left,right)
#     rightk=self.getrightK(data,k,left,right)
#     return rightk-leftk+1
# def getleftK(self,data,k,left,right):###查找重复数字中最左边的那个数字位置
#     while left<=right:
#         middle=(left+right)//2
#         if data[middle]<k:#k在左半边
#             left=middle+1
#         else:
#             right=middle-1
#     return left
# def getrightK(self,data,k,left,right):###查找重复数字最右边的那个数字位置
#     while left<=right:
#         middle=(left+right)//2
#         if data[middle]<=k:#k在右半边
#             left=middle+1
#         else:
#             right=middle-1
#     return right