代码

const int block_cnt = 16;

int guide[16];

#define g(i) guide[(i)] = a[n / block_cnt * (i)]
#define g0(i) g(i), g(i + 1)
#define g1(i) g0(i), g0(i + 2)
#define g2(i) g1(i), g1(i + 4)
#define g3(i) g2(i), g2(i + 8)

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(i) c((i), w((i) - 1), w((i)))
#define c1(i) c((i), c0((i) - 1), c0((i) + 1))
#define c2(i) c((i), c1((i) - 2), c1((i) + 2))
#define c3(i) c((i), c2((i) - 4), c2((i) + 4))

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

评测结果