统计一个数字在排序数组中出现的次数

最初的想法是用二分法找到第一个等于k的索引,然后分别向左和向右找相同的元素来确定左边界和右边界
但是如果左边和右边的相同的元素特别多的话,就还要遍历很多次
于是想到再用两次二分法分别求出左边界和右边界
整体时间复杂度为O(logn)

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        def get_first(data,l,r,k):
            while l<=r:
                mid=l+(r-l)//2
                if data[mid]==k and (mid==l or data[mid-1] != k):
                    return mid
                if data[mid]!=k:
                    l=mid+1
                else:
                    r=mid-1
        def get_last(data,l,r,k):
            while l<=r:
                mid=l+(r-l)//2
                if data[mid]==k and (mid==r or data[mid+1]!=k):
                    return mid
                if data[mid]!=k:
                    r=mid-1
                else:
                    l=mid+1
        l=0
        r=len(data)-1
        while l<=r:
            mid=l+(r-l)//2
            if data[mid]==k:
                return get_last(data,mid,r,k)-get_first(data,l,mid,k)+1
            if data[mid]<k:
                l=mid+1
            else:
                r=mid-1
        return 0