代码

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;
	
#define r \
	if (p[n] == x)\
		return p - a + n;\
	--n;\
	if (mid = (n * (long long)(x - *p) / (p[n] - *p)), p[mid] < x)\
		p += mid + 1, n -= mid + 1;\
	else\
		n = mid;
	r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r
	return -1;
}

int main()
{
	printf("%d\n", plus(2, 3));
	
	unsigned a[16] = {9, 8, 15, 77, 13, 1, 32, 4, 0, 6, 34, 23, 43, 72, 64, 28};
	
	sort(a, 16);
	
	for (int i = 0; i != 16; ++i)
		printf("%d ", a[i]);
	printf("\n");
	printf("%d\n", binary_search(a, 16, 0));
	
	return 0;
}

评测结果