对于一个项目，我需要实现二分搜索。这种二分查找允许重复。我必须获得与我的目标匹配的所有索引值。如果发现中间有重复项，我考虑过这样做:
目标=G 假设有以下排序数组:
B、D、E、F、G、G、G、G、G、G、Q、RS、S、Z
我得到的 mid 是 7。由于双方都有目标匹配，并且我需要所有目标匹配，所以我认为获取所有目标的一个好方法是检查 mid + 1 是否具有相同的值。如果是，请继续向右中间移动，直到不是为止。所以，结果会是这样的:
B、D、E、F、G、G、G、G、G、G (MID)、Q、RS、S、Z
然后我会从 0 到 mid 来计算目标匹配项，并将它们的索引存储到数组中并返回它。
如果中间是一个匹配项，并且重复项恰好第一次出现在中间且位于数组的两侧，那么我就是这么想的。
现在，如果第一次不匹配怎么办？例如:
B、D、E、F、G、G、J、K、L、O、Q、R、S、S、Z
然后像平常一样，它会抓取 mid，然后从第一个到 mid-1 调用二分搜索。
B、D、E、F、G、G、J
由于 G 大于 F，因此从 mid+1 到最后调用二分查找。
G、G、J。
中期是一场比赛。既然是匹配，则通过for循环从mid+1到last查找，统计匹配的个数，并将匹配索引存入数组并返回。
这是二分搜索抓取所有重复项的好方法吗？如果您发现我的算法存在问题，请告诉我，并提供提示/建议(如果有)。我看到的唯一问题是，如果所有匹配项都是我的目标，我基本上会搜索整个数组，但话又说回来，如果是这种情况，我仍然需要获取所有重复项。
谢谢
顺便说一句，我的老师说我们不能使用向量、哈希或其他任何东西。他希望我们停留在数组级别并习惯使用它们和操作它们。
最佳答案
为什么您一找到匹配项就想放弃二分搜索的强大功能？为什么不在上半部分使用二分查找并缩小范围，直到找不到更多的 G，然后对下半部分执行相同的操作。这样在最坏的情况下你就不会搜索整个数组。您可以通过这种方式找到最小和最大索引，然后将它们以及所有中间索引存储在一个数组中。
关于algorithm - 二分查找帮助，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2437353/