CODEWITHSUNDEEP
c++stlbinary-search
Miguel
Miguel

Reputation: 215

C++ partition_point that works with index information

Is there something in C++ that's basically equivalent to partition_point but in which I can use the indices as extra info?

For example, suppose I have a vector<int> X = {0,1,2,8,9,11} that I know is sorted and has only nonnegative integers, and I want the first index for which X[i] != i. How would I write a binary-search version of this? I know that the predicate X[i] == i returns true true true false false false.

If i didn't need to use the indices, I could just use std::partition_point. I could write my own, but, really, someone has probably already written a bug-free version.

Thanks.

Upvotes: 2

Views: 651

Answers (4)

Marian K.
Marian K.

Reputation: 359

use boost::counting_iterator

int solution(int K, int M, vector &A) {
    return *std::partition_point(counting_iterator(0),counting_iterator(M*A.size()),[K,&A](int ls){ return !checkLargeSum(ls,K,A);});
}

Upvotes: 1

Severin Pappadeux
Severin Pappadeux

Reputation: 20120

Well, std::lower_bound might work as well, and complexity guarantees to be O(log2(N))

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {0,1,2,8,9,11};

    auto i  = std::lower_bound(std::cbegin(v), std::cend(v), 0, [&](const int&e, const int&) { return e == (&e - std::addressof(v[0])); });

    std::cout << *i  << std::endl;

    return 0;
}

Upvotes: 0

Miguel
Miguel

Reputation: 215

Thanks all,

I ended up just copying the implementation of my compiler into a new function and removing one single *: _pred(*iter) -> _pred(iter) and using that new function.

Thanks again, your solutions probably work better.

Upvotes: 0

Jarod42
Jarod42

Reputation: 217810

You may try this version.

auto it = std::partition_point(std::begin(v), std::end(v),
              [&](const int& e) { return e == (&e - std::data(v)); });

Demo.

Not sure if we have guaranty than e is a reference of element of v.

Upvotes: 4

Related Questions