java - 有效地找到排序数组中的整数数量

Question

我正在备考，发现了这道题。

给定一个排序的整数数组，例如:

{-5, -5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99}

写一个方法:

Public static int count (int[] a, int x)

返回次数，数字'x'在数组中。

例如:

x = -5, it returns 2
x = 2, it returns 5
x = 8, it returns 0

我需要尽可能高效地编写它，请不要给我答案(或者随便写，我不看)，我的思路是做二分查找，然后转到我找到的值的两个边缘(向后和向前)并使用索引号，返回正确答案，我的问题是:

1. 这是最有效的方法吗？
2. 在最坏的情况下不会是 O(n) 吗？ (当数组填满单个数字时)-

如果是这样——那我为什么要进行二分查找呢？

Answer 1

修改您的二进制搜索以找到给定输入的第一次和最后一次出现，然后这两个索引之间的差异就是结果。

要使用二分查找查找第一个和最后一个匹配项，您需要对通常的二分查找算法稍作改动。在二进制搜索中，找到匹配项时返回值。但是这里不像通常的二进制搜索，你需要继续搜索直到找到不匹配的地方。

有用的链接

finding last occurence , finding first occurance

一些更新

找到第一个匹配项后，您可以使用该索引作为下一个二进制搜索的起点以找到最后一个匹配项。