二进制搜索递减列表？

Question

我有一个严格按递减顺序排序的数组和一个元素val；我想找到数组中最大元素的索引，该元素小于val（如果val已经存在，则为相等），并且我想在logn时间内完成此操作。和执行upper_bound()不是一个选项。

例如，如果数组为{10,5,3,1}而val为6，则函数应返回1。

我对迭代器是个新手，尝试过在upper_bound()中添加比较函数来使其工作，但失败了。我该怎么处理这件事。

注意：我检查了类似的问题之前，张贴和发现了一个，但不幸的是它涉及Java，所以。

Answer 1

使用upper_bound()，它将比较函数作为第四个参数。

Answer 2

只需将upper_bound与适当的比较函数一起使用：

• 您的列表是反向的(upper_bound通常要求顺序递增），因此您需要使用而不是<。
• 您希望包含搜索的元素（而upper_bound通常排除它），因此您需要使用>=而不是仅仅使用>。

. 

int data[] = {10,5,3,1};
auto item = std::upper_bound(std::begin(data), std::end(data), 6,
                             [](int a, int b) { return a >= b; });

现在您只需将结果迭代器转换为索引（在检查其有效之后）：

if (item != std::end(data)) {
    auto index = std::distance(std::begin(data), item);
    std::cout << index << std::endl;
}
else
    std::cout << "not found" << std::endl;