二分查找帮助
对于一个项目，我需要实现二分搜索。这种二分查找允许重复。我必须获得与我的目标匹配的所有索引值。如果发现中间有重复项，我考虑过这样做：
Target = G 假设有以下排序数组：
B，D，E，F，G，G，G，G，G，G，Q，RS，S，Z
我得到的中间值是 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，然后从first到mid调用二分查找-1。
B、D、E、F、G、G、J
由于 G 大于 F，因此从 mid+1 到最后调用二分查找。
G、G、J。
中间是一场比赛。既然是匹配，则通过for循环从mid+1到last查找，统计匹配的个数，并将匹配索引存入数组并返回。
这是二分搜索抓取所有重复项的好方法吗？如果您发现我的算法存在问题，请告诉我，并提供提示/建议（如果有）。我看到的唯一问题是，如果所有匹配项都是我的目标，我基本上会搜索整个数组，但话又说回来，如果是这种情况，我仍然需要获取所有重复项。
谢谢
顺便说一句，我的老师说我们不能使用向量、哈希或其他任何东西。他希望我们停留在数组层面并习惯于使用它们和操纵它们。
for a project I need to implement a binary search. This binary search allows duplicates. I have to get all the index values that match my target. I've thought about doing it this way if a duplicate is found to be in the middle:
Target = G
Say there is this following sorted array:
B, D, E, F, G, G, G, G, G, G, Q, R S, S, Z
I get the mid which is 7. Since there are target matches on both sides, and I need all the target matches, I thought a good way to get all would be to check mid + 1 if it is the same value. If it is, keep moving mid to the right until it isn't. So, it would turn out like this:
B, D, E, F, G, G, G, G, G, G (MID), Q, R S, S, Z
Then I would count from 0 to mid to count up the target matches and store their indexes into an array and return it.
That was how I was thinking of doing it if the mid was a match and the duplicate happened to be in the mid the first time and on both sides of the array.
Now, what if it isn't a match the first time? For example:
B, D, E, F, G, G, J, K, L, O, Q, R, S, S, Z
Then as normal, it would grab the mid, then call binary search from first to mid-1.
B, D, E, F, G, G, J
Since G is greater than F, call binary search from mid+1 to last.
G, G, J.
The mid is a match. Since it is a match, search from mid+1 to last through a for loop and count up the number of matches and store the match indexes into an array and return.
Is this a good way for the binary search to grab all duplicates? Please let me know if you see problems in my algorithm and hints/suggestions if any. The only problem I see is that if all the matches were my target, I would basically be searching the whole array but then again, if that were the case I still would need to get all the duplicates.
Thank you
BTW, my instructor said we cannot use Vectors, Hash or anything else. He wants us to stay on the array level and get used to using them and manipulating them.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
为什么一找到匹配项就想放弃二分搜索的强大功能呢？为什么不对上半部分使用二分查找并缩小范围，直到找不到更多的 G，然后对下半部分执行相同的操作。这样在最坏的情况下你就不会搜索整个数组。您可以通过这种方式找到最小和最大索引，然后将这些索引加上所有中间索引存储在一个数组中。
Why do you want to get away from what makes Binary search so great as soon as you find a match? Why not use a binary search on the upper half and narrow it down until you don't get any more G's, then do the same with the lower. That way in the worst case you're not searching the whole array. You find the min and max index in this way, then store those plus all of the intermediate ones in an array.
参考stl中lower_bound函数的源代码。
如果您手头或学校图书馆有一本《Programming Pearls》，请参阅本书末尾的第四章及其解决方案。
Ref to the source code of lower_bound function in stl.
If you have a copy of Programming Pearls at hand or in the school library, refer to the 4th chapter and its solutions at the end of the book.
我使用修改后的数组二分搜索算法的解决方案回答了这个问题 。由于这是家庭作业，除非您希望它被破坏，否则不要单击该链接，但要点是，通过修改二分搜索循环中的条件，您可以让它执行以下 3 种行为中的任何一种：
然后通过运行这个二分搜索两次来回答你的问题，一次找到最左边的匹配，然后再次找到最右边的匹配（仅当第一次运行成功时）。两个结果之间的差值（即匹配索引）比找到的总匹配数少 1。
I answered this question with a solution that uses a modified binary search algorithm for arrays. As this is homework, don't click the link unless you want it spoiled, but the gist is that by tinkering with the conditions in a binary search loop, you can get it to do any of the following 3 behaviors:
Then your question is answered by running this binary search twice, once to find the left-most match and then again to find the right-most match (only if the first run succeeded). The difference between the two results, i.e. match indices, is 1 less than the number of total matches found.
请注意，您不是在搜索元素 X，而是在搜索边界 Y,X，其中 Y < X 和 X,Z 对称，其中 X＜1 Z. 这些边界也可以通过二分查找在由元素间边界组成的假想数组中找到。
Notice that you're not searching for an element X, but you're searching for a boundary Y,X where Y < X and symmetrically for X,Z where X < Z. These boundaries may also be found with binary search in an imaginary array consisting of inter-element boundaries.