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

Question

仅仅使用二进制搜索，如何获得带有重复项的请求元素，因为重复项将是一个接一个的，搜索的条件是什么？
可以说这是由用户输入的给定数组，我们必须搜索“efg”是否存在，我们不知道索引，也不重复重复多少次，但是如果存在，则打印重复次数。

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

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计算no。实例。