对于一个项目，我需要实现二进制搜索 . 这种二进制搜索允许重复 . 我必须获得与我的目标匹配的所有索引值 . 如果发现副本位于中间，我已经考虑过这样做：
Target = G假设有以下排序数组：
B，D，E，F，G，G，G，G，G，G，Q，R S，S，Z
我得到了7的中间 . 由于双方都有目标匹配，并且我需要所有目标匹配，我认为如果它是相同的值，那么获得所有目标的好方法是检查中间1 . 如果是的话，继续向右移动，直到不是 . 所以，它会像这样：
B，D，E，F，G，G，G，G，G，G（MID），Q，R S，S，Z
然后我会从0到中间计数来计算目标匹配并将它们的索引存储到一个数组中并返回它 .
这就是我想要做的事情，如果mid是匹配的，那么副本恰好是在第一次中间和阵列的两侧 .
现在，如果第一次不匹配怎么办？例如：
B，D，E，F，G，G，J，K，L，O，Q，R，S，S，Z
然后正常情况下，它会 grab mid，然后从第一个到第一个中间调用二进制搜索 .
B，D，E，F，G，G，J
由于G大于F，因此从中间1到最后调用二进制搜索 .
G，G，J .
中期是一场比赛 . 由于它是匹配项，因此从中间1到最后通过for循环搜索并计算匹配数并将匹配索引存储到数组中并返回 .
这是二进制搜索 grab 所有重复项的好方法吗？如果您发现我的算法存在问题，请通知我 . 如果有的话，请提示/建议 . 我看到的唯一问题是，如果所有的匹配都是我的目标，我基本上会搜索整个数组但是再次，如果是这种情况，我仍然需要获得所有重复 .
谢谢
顺便说一句，我的导师说我们不能使用Vectors，Hash或其他任何东西 . 他希望我们留在阵列级别并习惯使用它们并操纵它们 .
5 回答
看看this past question . 接受的答案使用STL，但其他一些答案有一些可能对您有帮助的信息 .
参考stl中lower_bound函数的源代码 .
如果您手头或学校图书馆有编程珍珠的副本，请参阅本书末尾的第4章及其解决方案 .
我用一个使用修改后的二进制搜索算法的解决方案回答了this question . 由于这是家庭作业，除非你想要它被破坏，否则不要点击链接，但要点是通过修改二进制搜索循环中的条件，你可以让它做以下3种行为中的任何一种：
在找到匹配的那一刻返回一个匹配（正常行为，匹配可以是一系列相同值中的任何位置）
返回最左边的比赛
返回最右边的比赛
然后通过运行此二进制搜索两次来回答您的问题，一次找到最左侧的匹配，然后再次找到最右侧的匹配（仅当第一次运行成功时） . 两个结果之间的差异，即匹配指数，比找到的总匹配数少1 .
为什么你想在找到匹配后立即摆脱使Binary搜索变得如此之大的原因？为什么不在上半部分使用二进制搜索并缩小它直到你不再获得更多的G，然后用更低的值做同样的事情 . 在最糟糕的情况下，你不会搜索整个阵列 . 您可以通过这种方式找到最小和最大索引，然后将这些索引以及所有中间索引存储在数组中 .
请注意，您没有搜索元素X，但是您正在搜索边界Y，X，其中Y <X并且对称地搜索X，Z，其中X <Z . 这些边界也可以在虚构中使用二分搜索找到由元素间边界组成的数组 .