劍指Offer（37）：數字在排序數組中出現的次數

一、引子

這個系列是我在牛客網上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。

二、題目

統計一個數字在排序數組中出現的次數。

1、思路

看見有序，肯定就是二分查找了

做法就是使用二分法找到數字在數組中出現的第一個位置，再利用二分法找到數字在數組中出現的最后一個位置。時間復雜度為O(logn + logn)，最終的時間復雜度為O(logn)。

舉個例子，找到數字k在數組data中出現的次數。

數組data中，數字k出現的第一個位置：

我們對數組data進行二分，如果數組中間的數字小于k，說明k應該出現在中間位置的右邊；如果數組中間的數字大于k，說明k應該出現在中間位置的左邊；如果數組中間的數字等于k，并且中間位置的前一個數字不等于k，說明這個中間數字就是數字k出現的第一個位置。

同理，數字k出現的最后一個位置，也是這樣找的。但是判斷少有不同。我們使用兩個函數分別獲得他們。

2、編程實現

python

代碼實現方案：
python有自帶的方法進行查找~

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return data.count(k)

分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！

本文由博客一文多發平臺 OpenWrite 發布！

審核編輯 黃昊宇