原标题：剑指Offer（三十七）：数字在排序数组中出现的次数

原文来自：博客园      原文链接：https://www.cnblogs.com/aimi-cn/p/11683577.html

剑指Offer（三十七）：数字在排序数组中出现的次数

一、引子

这个系列是我在牛客网上刷《剑指Offer》的刷题笔记，旨在提升下自己的算法能力。
查看完整的剑指Offer算法题解析请点击CSDN和github链接：
剑指Offer完整习题解析CSDN地址
github地址

二、题目

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

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)

本文由博客一文多发平台 OpenWrite 发布！

免责声明：本文来自互联网新闻客户端自媒体，不代表本网的观点和立场。

合作及投稿邮箱：E-mail:editor@tusaishared.com