二分法

由于是有序序列，可用二分法查寻目标数值k所在位置，再往前和往后统计k的数量

# @param data int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        if len(data) == 0:
            return 0
        # 二分法
        p,q = 0,len(data)
        while p != q:
            mid = int((p+q)/2)
            if data[mid] == k: # 找到k
                # 统计k出现的次数
                ks = 1
                i = mid - 1
                j = mid + 1
                # 往前
                while i >= 0 and data[i] == k:
                    i -= 1
                    ks += 1
                # 往后
                while j <= len(data) - 1 and data[j] == k:
                    j += 1
                    ks += 1
                return ks
            elif data[mid] > k: # k位于mid的左侧
                q = mid - 1
            else: # k为mid的右侧
                p = mid + 1
        return 0