# -*- coding:utf-8 -*-

class Solution:

    def GetNumberOfK(self, data, k):

        # write code here

        number = 0

        if data !=None and len(data)>0:

            length=len(data)

            first = self.GetFirst(data,length,k,0,length-1)

            last = self.GetLast(data,length,k,0,length-1)

            if first > -1 and last > -1:

                number=last-first+1

        return number

    def GetFirst(self,data,lenth,k,start,end):

        if start>end:

            return -1

        middle = (start+end)//2

        if data[middle]==k:

            if middle>0 and data[middle-1]==k:

                end = middle -1

            else:

                return middle

        elif data[middle]>k:

            end=middle-1

        else:

            start=middle+1

        return self.GetFirst(data,lenth,k,start,end)

    def GetLast(self, data, lenth, k, start, end):

        if start>end:

            return -1

        middle=(start+end)//2

        if data[middle]==k:

            if middle<end and data[middle+1]==k:

                start = middle+1

            else:

                return middle

        elif data[middle]>k:

            end=middle-1

        else:

            start=middle+1

        return self.GetLast(data, lenth, k, start, end)