代码

int guide[16];

//#define g(i) guide[i] = a[n / 16 * 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);
guide[1] = a[n / 16 * 1];
guide[2] = a[n / 16 * 2];
guide[3] = a[n / 16 * 3];
guide[4] = a[n / 16 * 4];
guide[5] = a[n / 16 * 5];
guide[6] = a[n / 16 * 6];
guide[7] = a[n / 16 * 7];
guide[8] = a[n / 16 * 8];
guide[9] = a[n / 16 * 9];
guide[10] = a[n / 16 * 10];
guide[11] = a[n / 16 * 11];
guide[12] = a[n / 16 * 12];
guide[13] = a[n / 16 * 13];
guide[14] = a[n / 16 * 14];
guide[15] = a[n / 16 * 15];
	return 0;
}

#define c(i, a, b) if (x < guide[i]) a else b
#define w(i) p = a + n / 16 * i, n = n / 16 * (i + 1) - n / 16 * 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;
}

评测结果