二进制搜索减少列表? [英] Binary searching a decreasing list?

问题描述

我有一个严格按降序排列的数组和一个元素 val ；我想在小于val的数组中找到最大元素的索引(或者如果val已经存在，则等于)，我想在 login 时间内这样做.反转数组并执行upper_bound()也不是可行的选择.

I have an array sorted in strictly decreasing order and an element val; i want to find the index of largest element in the array which is less than val(or equal if val already exists there) and i want to do so in logn time. And reversing the array and doing upper_bound() is not an option.

例如.如果array为{10,5,3,1}且val为6，则该函数应返回1.

Eg. if array is {10,5,3,1} and val is 6, the function should return 1.

我真的是迭代器的新手，尝试过在upper_bound()中添加比较函数以使其工作，但失败了.我应该怎么做.

I am really new to iterators and tried something like adding a comparison function in upper_bound() to make it work but it failed. How should I go about this.

注意:我在发布之前检查了类似的问题，但发现一个问题，但不幸的是，它与Java有关.

Note: I checked for similar questions prior to posting and found one but unfortunately it pertained to Java, so.

推荐答案

只需将 upper_bound 与适当的比较功能配合使用:

Just use upper_bound with the proper comparison function:

• 您的列表是相反的( upper_bound 通常期望顺序递增)，因此您需要使用> 而不是< .
• 您要包括搜索到的元素(而 upper_bound 通常会排除它)，因此您需要使用> = 而不是仅仅使用> .

• Your list is reversed (upper_bound usually expects increasing order) so you need to use > rather than <.
• You want to include the searched element (while upper_bound usually excludes it) so you need to use >= rather than mere >.

.

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; });

现在，您只需要将生成的迭代器转换为索引(在检查其有效之后即可):

Now you only have to convert the resulting iterator to an index (after checking it is valid):

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;

这篇关于二进制搜索减少列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！