algorithm - 二进制搜索帮助

Question

对于一个项目，我需要实现二分查找。此二进制搜索允许重复。我必须获得与我的目标匹配的所有索引值。如果发现中间有重复项，我考虑过这样做:

目标 = G假设有以下排序数组:

B, D, E, F, G, G, G, G, G, G, Q, R S, S, Z

我得到的 mid 是 7。由于双方都有目标匹配，而且我需要所有目标匹配，所以我认为获取所有目标的一个好方法是检查 mid + 1 是否具有相同的值。如果是，请继续向右移动直到不是。所以，结果会是这样的:

B, D, E, F, G, G, G, G, G, G (MID), Q, R S, S, Z

然后我会从 0 到 mid 计数以计算目标匹配并将它们的索引存储到一个数组中并返回它。

这就是我的想法，如果 mid 是一个匹配项并且副本第一次恰好在中间并且在数组的两侧。

---

现在，如果第一次不匹配怎么办？例如:

B、D、E、F、G、G、J、K、L、O、Q、R、S、S、Z

然后像往常一样，它会抓取 mid，然后调用从 first 到 mid-1 的二分查找。

B、D、E、F、G、G、J

由于G大于F，从mid+1到last调用二分查找。

G, G, J.

中间是一场比赛。既然是匹配，就通过for循环从mid+1到last查找，统计匹配的个数，将匹配索引存入数组返回。

这是二进制搜索抓取所有重复项的好方法吗？如果您在我的算法中发现问题和提示/建议(如果有)，请告诉我。我看到的唯一问题是，如果所有匹配项都是我的目标，我基本上会搜索整个数组，但话又说回来，如果是这种情况，我仍然需要获取所有重复项。

谢谢

顺便说一句，我的导师说我们不能使用 Vectors、Hash 或其他任何东西。他希望我们停留在阵列层面，习惯于使用和操纵它们。

Answer 1

为什么您一找到匹配项就想摆脱使二分搜索如此强大的原因？为什么不在上半部分使用二分搜索并缩小范围，直到你不再得到任何 G，然后对下半部分做同样的事情。这样在最坏的情况下你不会搜索整个数组。您以这种方式找到最小和最大索引，然后将它们加上所有中间索引存储在一个数组中。