題目：

統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。例如，輸入排序數(shù)組{1, 2, 3, 3, 3, 3, 4, 5}和數(shù)字3，由于3在這個(gè)數(shù)組中出現(xiàn)了4次，因此輸出4。

思路：

既然輸入的數(shù)組是排序的，那么我們就能很自然的想到用二分查找算法。在題目給出的例子中，我們可以先用二分查找算法找到一個(gè)3。由于3可能出現(xiàn)多次，因此我們找到的3的左右兩邊可能都有3，于是在找到的3的左右兩邊順序掃描，分別找出第一個(gè)3和最后一個(gè)3，因?yàn)橐檎业臄?shù)字的長度位n的數(shù)組中有可能出現(xiàn)O(n)次，所以順序掃描的時(shí)間復(fù)雜度是O(n)。因此，這種算法的效率和直接從頭到尾順序掃描整個(gè)數(shù)組統(tǒng)計(jì)3出現(xiàn)的次數(shù)的方法是一樣的。

接下來我們思考如何更好的利用二分查找算法，假設(shè)我們要統(tǒng)計(jì)數(shù)字k在排序數(shù)組中出現(xiàn)的次數(shù)，在前面的算法中，時(shí)間主要消耗在如何確定重復(fù)出現(xiàn)的數(shù)字的第一個(gè)k和最后一個(gè)k的位置上，有沒有可能用二分查找算法直接找到第一個(gè)k及最后一個(gè)k呢?

我們先分析如何用二分查找算法在數(shù)組中找到第一個(gè)k，二分查找算法總是先拿數(shù)組中間的數(shù)字和k作比較。如果中間的數(shù)字比k大，那么k只有可能出現(xiàn)在數(shù)組的前半段，下一輪我們只在數(shù)組的前半段查找就可以了。如果中間的數(shù)字比k小，那么k只有可能出現(xiàn)在數(shù)組的后半段，下一輪我們只在數(shù)組的后半段查找就可以了。如果中間的數(shù)字和k相等，我們先判斷這個(gè)數(shù)字是不是第一個(gè)k。如果中間數(shù)字的前面一個(gè)數(shù)字不是k，那么此時(shí)中間的數(shù)字剛好就是第一個(gè)k；如果中間數(shù)字的前面一個(gè)數(shù)字也是k，那么第一個(gè)k肯定在數(shù)組的前半段，下一輪我們?nèi)匀恍枰跀?shù)組的前半段查找。

基于同樣的思路，我們可以在排序數(shù)組中找到最后一個(gè)k。在分別找到第一個(gè)k和最后一個(gè)k的下標(biāo)之后，我們就能計(jì)算出k在數(shù)組中出現(xiàn)的次數(shù)。

python代碼如下：

class Solution:
    def GetNumberOfK(self, data, k):
        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:
                number =last -first +1
        return number
    
    def GetFirst(self, data, length, 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, length, k, start, end)
    
    def GetLast(self, data, length, 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, length, k, start, end)

此外，python中可以直接利用count函數(shù)，count函數(shù)是順序查找，最壞時(shí)間復(fù)雜度是O(n)

python代碼如下：

class Solution:
    def GetNumberOfK(self, data, k):
        return data.count(k)

更多精彩，關(guān)注“咋家”