Binary searching a decreasing list?

Question

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.

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

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.

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

Answer 1

Just use upper_bound with the proper comparison function:

• 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;