37. 数字在排序数组中出现的次数

题目描述
统计一个数字在排序数组中出现的次数。

思路
思路一：
暴力解，遍历数组并对比，一个循环，时间复杂度为
思路二：
由于数组是一个排序过的数组，所以可以用二分查找法，定位k的第一次出现位置和最后一次出现位置，时间复杂度为

代码实现
暴力解，遍历数组

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        count = 0
        for i in range(len(data)):
            if(data[i] == k):
                count += 1
        return count
        # 或者就直接用python的count函数
        # return data.count(k)

二分查找法：

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        def getFirst(data,k):
            left = 0
            right = len(data)-1
            while(right >= left):
                if(data[left] == k):
                    return left
                mid = (right+left)//2
                if(data[mid] > k):
                    right = mid - 1
                elif(data[mid] < k):
                    left = mid + 1
                else:
                    if(data[mid] == k and data[mid-1]!=k):
                        return mid
                    right = mid - 1
            return -1

        def getLast(data,k):
            left = 0
            right = len(data)-1
            while(right >= left):
                if(data[right] == k):
                    return right
                mid = (right+left)//2
                if(data[mid] > k):
                    right = mid - 1
                elif(data[mid] < k):
                    left = mid + 1
                else:
                    if(data[mid] == k and data[mid+1]!=k):
                        return mid
                    left = mid + 1
            return -1       

        num = 0
        if data:
            first = getFirst(data,k)
            print(first)
            last = getLast(data,k)
            print(last)
            if(first > -1 and last > -1):
                num = last - first + 1
                return num
        return num

python二分查找法
评论中指出了两个问题，已修正，注意python整除要用//，while中的比较用<=
链接中的代码有错误，仅供参考

def BinarySearch(array,t):
    low = 0
    height = len(array)-1
    while low <= height:
        mid = (low+height)//2
        if array[mid] < t:
            low = mid + 1

        elif array[mid] > t:
            height = mid - 1

        else:
            return array[mid]

    return -1

python二分查找法