f2lk6wf90d's blog

Using the C++ standard library for binary search
By f2lk6wf90d, history, 8 years ago, In English

In C, it's possible to use the bsearch() function to perform binary search on a 'hidden' array. e.g. for IOI 2015 practice — Search (part of task description below):

You may call a function compare(i, val) that compares number Ai and integer number val. This function returns:
-  - 1: if Ai > val
- 1 if Ai < val
- 0 if Ai = val.

Now, bsearch() can be used like this: 

int values[1000];
int cmp(const int * a, const int * b)
{
   int id = b - values;
   return compare(id, *a); 
}
int find(int sub, int N, int X) {
    int* ptr = bsearch(&X, values, N, sizeof(int), cmp);
    return ptr == NULL ? -1 : ptr - values;
}

Is something like this possible using std::lower_bound?

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I think you can use lower_bound with custom comparator to achieve same goal. As the array is "hidden", I'd call it on a manually crafted array containing 0, 1, 2, etc, so the comparator can understand which index it's called on.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if r==10^18?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can implement your own random-access iterators and pass them to lower_bound. I think it's not worth it during a competition — it will be much more code than to implement lower_bound yourself.

      → Reply