c++ - 二进制搜索递减列表？

Question

我有一个按严格降序排序的数组和一个元素val；我想找到数组中小于 val 的最大元素的索引（如果 val 已经存在，则等于）并且我想及时这样做logn。并且反转数组并执行 upper_bound() 不是一种选择。

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

我对迭代器真的很陌生，并尝试过在 upper_bound() 中添加一个比较函数以使其工作，但它失败了。我该怎么办。

注意：我在发布之前检查了类似的问题并找到了一个，但不幸的是它与 Java 有关，所以。

Answer 1

只需使用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;

Answer 2

对于迭代方式，我可能会val从数组末尾开始搜索值。IE：

int indexFinder(int array[], int arraySize, int val){
    for(int i = (val >= arraySize ? 0 : (arraySize - val)); i < arraySize; ++i){
        if(array[i] <= val) return i;
    }
}

这个循环的一个关键是，一旦它遇到任何小于或等于的值，它就会返回索引，将它限制为它找到的第一种情况。

它还检查是否val大于最大的数组索引。

Answer 3

使用upper_bound()带有比较功能的 ，因为它是第四个参数。