代码

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;
}

评测结果