constexpr int BOLCKS = 16;
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 += 4)
{
table[i] = a[block_len * i];
table[i + 1] = a[block_len * (i + 1)];
table[i + 2] = a[block_len * (i + 2)];
table[i + 3] = a[block_len * (i + 3)];
}
}
}
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;
// }
for (int i = 0; i < BOLCKS; ++i)
{
if (table[i] > x)
{
return i - 1;
}
}
return BOLCKS - 1;
}
int binary_search(const unsigned *a, int n, const unsigned x)
{
init(a, n);
const int block_len = n / BOLCKS;
unsigned long long l = search_block(x), r = l + 1;
l *= block_len;
if (r == BOLCKS)
{
r = n - 1;
}
else
{
r *= block_len;
}
while (l < r)
{
unsigned long long l_num = a[l];
unsigned long long r_num = a[r];
unsigned long long mid = (r * (x - l_num) + l * (r_num - x)) / (r_num - l_num);
unsigned long long mid_num = a[mid];
if (mid_num == x)
{
return mid;
}
else if (mid_num < x)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return l;
}