题解 | #数字在升序数组中出现的次数#

暴力求解和使用二分法游标进行求解

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
#     def GetNumberOfK1(self , data: List[int], k: int) -> int:
#         # write code here2，
#         # 暴力jiefa，直接搜索匹配
#         count = 0
#         for i in data:
#             if i==k:
#                 count = count+1
#         return count
#     # 但是有时间复杂度的要求，且数据中的数据是已经排好顺序的
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        # 对于一个有序的序列，直接查找其左边界和相应的右边界，然后边界相减就可
        letf = 0
        right = len(data)-1
        #mid = (letf + right-1)/2
        while letf<=right:
            mid = (letf + right)//2
            if data[mid] < k:
                letf = mid + 1
            elif data[mid] > k:
                right = mid - 1
            else:
                right = mid -1
        l = right
        
        letf = 0
        right = len(data)-1
        #mid = (letf + right-1)/2
        while letf<=right:
            mid = (letf + right)//2
            if data[mid] < k:
                letf = mid + 1
            elif data[mid] > k:
                right = mid - 1
            else:
                letf = mid + 1
                
        r = letf-1
        return r - l