代码

const int block_cnt = 24;

int guide[24];

#define g(i) guide[i] = a[n / block_cnt * i]
#define g0(x) g(x), g(x + 1), g(x + 2)
#define g1(x) g0(x), g0(x + 3)
#define g2(x) g1(x), g1(x + 6)
#define g3(x) g2(x), g2(x + 12)

int init(const unsigned *a, const int n)
{
	g3(0);
	return 0;
}

#define w(i) p = a + n / block_cnt * i, n = n / block_cnt * (i + 1) - n / block_cnt * i - 1;
#define c(i, a, b) if (x < guide[i]) a else b
#define c0(x) c(x, w(x - 1), c(x + 1, w(x), w(x + 1)))
#define c1(x) c(x, c0(x - 2), c0(x + 1))
#define c2(x) c(x, c1(x - 3), c1(x + 3))
#define c3(x) c(x, c2(x - 6), c2(x + 6))

int binary_search(const unsigned *a, int n, const unsigned x)
{
	static int _ = 1;
	if (_)
		init(a, n), _ = 0;
	
	const unsigned *p;
	
	c3(12);
	
	int mid;
	--n;
	while (p[n] != x)
		if (mid = (n * (long long)(x - *p) / (p[n] - *p)), p[mid] < x)
			p += mid + 1, n -= mid + 1;
		else
			n = mid;
	return p - a + n;
}

评测结果