面试题:数字在排序数组中出现的次数题目：统计一个

参考答案:

正确答案：

既然输入的数组是排序的，那么我们很自然地就能想到用二分查找算法。在题目给出的例子中，我们可以先用二分查找算法找到一个3。由于3可能出现多次，因此我们找到的3的左右两边可能都有3，于是我们在找到的3的左右两边顺序扫描，分别找出第一个3和最后一个3。因为要查找的数字在长度为n的数组中有可能出现O(n)次，所以顺序扫描的时间复杂度是O(n)。因此这种算法的效率和直接从头到尾顺序扫描整个数组统计3出现的次数的方法是一样的。显然，面试官不会满意这个算法，他会提示我们还有更快的算法。
接