算法1

(二分查找) $O(log(n))$

python 代码

class Solution(object):
    def getNumberOfK(self, nums, k):
        """
        :type nums: list[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return 0
        l,r=0,len(nums)-1
        mid=0
        while l<r:
            mid=(l+r)//2
            if nums[mid]==k:
                break
            if nums[mid]>k:
                r=mid
            else:
                l=mid+1
        c=0
        tl,tr=mid,mid+1
        while tl>=0 and nums[tl]==k:
            c+=1
            tl-=1
        while tr<len(nums) and nums[tr]==k:
            c+=1
            tr+=1
        return c