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?