• 一种投机取巧的思想：因为data中都是整数，利用二分法搜索k-0.5和k+0.5这两个数应该插入的位置，然后相减即可。注意是start <= end
    class Solution:
  def GetNumberOfK(self, data, k):
      # write code here
      return self.biSearch(data, k+0.5) - self.biSearch(data, k-0.5)
  def biSearch(self, data, num):
      start = 0
      end = len(data) - 1
      while start <= end:
          mid = (end - start)/2 + start
          if data[mid] < num:
              start = mid + 1
          elif data[mid] > num:
              end = mid - 1
      return start

  • 正经做法：
    利用二分法，寻找第一个和最后一个出现的k
    以寻找第一个为例，
    如果mid刚好等于k：

    1. 此时mid == index1,返回mid

    2. mid > index1，mid-1不等于k，此时mid依然为k第一次出现的位置，返回mid

    3. mid-1也等于k,此时说明第一个k出现在[index1，mid -1]区间内，继续进行二分查找 

      class Solution:
def GetNumberOfK(self, data, k):
 # write code here
 if not data :
     return 0
 first = self.getfirst(data,k)
 end = self.getend(data,k)
 if first > -1 and end >-1 :
     return end - first + 1
 else:
     return 0
def getfirst(self,data,k):
 lenth = len(data)
 index1 = 0
 index2 = lenth - 1
 while index1 <= index2:
     mid = (index2 - index1) // 2 + index1
     if data[mid] == k :
         if (mid > index1 and data[mid - 1] != k) or mid == index1:
             return mid
         else :
             index2 = mid - 1
     elif data[mid] > k:
         index2 = mid - 1
     else:
         index1 = mid + 1
 return -1 

def getend(self,data,k):
 lenth = len(data)
 index1 = 0
 index2 = lenth - 1
 while index1 <= index2:
     mid = (index2 - index1) // 2 + index1
     if data[mid] == k :
         if (mid < index2 and data[mid + 1] != k) or mid == index2:
             return mid
         else :
             index1 = mid + 1
     elif data[mid] > k:
         index2 = mid - 1
     else:
         index1 = mid + 1
 return -1