Using the C++ standard library for binary search

Revision en1, by f2lk6wf90d, 2017-03-24 23:47:54

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English f2lk6wf90d 2017-03-24 23:47:54 800 Initial revision (published)