代码

const int block_cnt = 16;

int guide[16];

#define g(i) guide[i] = a[n / block_cnt * i]

int init(const unsigned *a, const int n)
{
	g(1), g(2), g(3), g(4), g(5), g(6), g(7), g(8), g(9), g(10), g(11), g(12), g(13), g(14), g(15);
	return 0;
}

#define c(i, a, b) if (x < guide[i]) a else b
#define w(i) p = a + n / block_cnt * i, n = n / block_cnt * (i + 1) - n / block_cnt * i - 1;

int binary_search(const unsigned *a, int n, const unsigned x)
{
	static int _ = 1;
	if (_)
		init(a, n), _ = 0;
	
	const unsigned *p;
	
	c(8, c(4, c(2, c(1, w(0), w(1)), c(3, w(2), w(3))), c(6, c(5, w(4), w(5)), c(7, w(6), w(7)))), c(12, c(10, c(9, w(8), w(9)), c(11, w(10), w(11))), c(14, c(13, w(12), w(13)), c(15, w(14), w(15)))))
	
	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;
}

评测结果