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?
I think you can use
lower_boundwith custom comparator to achieve same goal. As the array is "hidden", I'd call it on a manually crafted array containing0,1,2, etc, so the comparator can understand which index it's called on.if r==10^18?
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 implementlower_boundyourself.