constexpr int BOLCKS = 64;
int table[BOLCKS];
void init(const unsigned *a, int n)
{
static bool is_init = false;
if (!is_init)
{
is_init = true;
const int block_len = n / BOLCKS;
for (int i = 0; i < BOLCKS; ++i)
{
table[i] = a[block_len * i];
}
}
}
int search_block(const unsigned x)
{
int l = -1, r = BOLCKS, m = (l + r) / 2;
while (m > l)
{
if (table[m] > x)
{
r = m;
}
else
{
l = m;
}
m = (l + r) / 2;
}
return l;
}
int binary_search(const unsigned *a, int n, const unsigned x)
{
init(a, n);
const int block_len = n / BOLCKS;
int l = search_block(x), r = l + 1;
l *= block_len;
if (r == BOLCKS)
{
r = n;
}
else
{
r *= block_len;
}
int m = (l + r) / 2;
while (m > l)
{
if (a[m] > x)
{
r = m;
}
else
{
l = m;
}
m = (l + r) / 2;
}
return l;
}