二进制搜索递减列表？

我有一个按严格递减顺序排列的数组和一个元素val;我想要找到数组中最大元素的索引，它小于val（或者如果val已经存在那里，则等于），并且我想在logn时间内这样做。并且颠倒数组并且执行upper_bound（）不是一个选项。二进制搜索递减列表？

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

我对迭代器非常陌生，尝试了在upper_bound（）中添加比较函数以使其工作但它失败了。我应该如何去解决这个问题。

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

来源

2013-08-21 ofey

是[这]（http://www.cplusplus.com/reference/算法/ upper_bound /）页面示例没有帮助？ – P0W

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

来源

2013-08-21 13:47:59 syam

你可以考虑使用'rbegin（）'和'rend（）'并且延长客户比较器。（可以肯定的是，无论如何它都可以工作;还没有尝试过，但它是铅笔）。 – WhozCraig

@WhozCraig事实上，这将适用于提供'rbegin/rend'但使用遗留数组的适当容器，我不确定如何正确获得'reverse_iterator'对（但必须有一种方法）。 – syam

是的，但无论如何，这工作。 +1 btw。 – WhozCraig

使用upper_bound()，它在出现arg时采用比较函数。

来源

2013-08-21 13:37:52

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

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是否大于最大数组索引。

来源

2013-08-21 13:47:31 Shade

二进制搜索递减列表？

回答

相关问题