c++ - 如何使用二进制搜索打印排序数组中的所有重复字符串？

Question

只是使用二分搜索，如何获得具有重复项的请求元素，因为重复项将一个接一个，搜索的条件应该是什么？

假设这是给定的数组，由用户输入，我们必须搜索“efg”是否存在，我们不知道索引，也不知道它重复了多少次，但如果存在，则打印倍其重复次数。

array[][10]={"abc","efg","efg","jkl","jkl","jhk"}

标签： c++calgorithmsearchbinary-search

Answer 1

您可以使用查找大于它upper_bound之后的第一个元素并查找 的第一个实例。"efg"lower_bound"efg"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<string> V{ "abc", "efg", "efg", "jkl", "jkl", "jhk" };
    cout << upper_bound(V.cbegin(), V.cend(), "efg") - lower_bound(V.cbegin(), V.cend(), "efg") << endl;
}

编辑：为了改进它，您可以首先使用lower_bound检查字符串是否存在于数组中。如果确实如此，则用于upper_bound计算编号。的实例。