代码

static unsigned xs[100];
static int ans[100];
static int done = 0;
static int cnt = 0;
static void solve(const unsigned *a, int n)
{
    int lo[100], hi[100], mid[100]; int i;
    for (i = 0; i < 100; i++) { lo[i] = 0; hi[i] = n - 1; }
    for (i = 0; i < 100; i++) { mid[i] = (lo[i] + hi[i]) >> 1; __builtin_prefetch(a + mid[i]); }
    for (int L = 0; L < 27; L++) {
        for (i = 0; i < 100; i++) {
            int m = mid[i];
            __builtin_prefetch(a + ((lo[i] + m) >> 1));
            __builtin_prefetch(a + ((m + hi[i]) >> 1));
        }
        for (i = 0; i < 100; i++) {
            unsigned v = a[mid[i]];
            if (v < xs[i]) { lo[i] = mid[i] + 1; mid[i] = (lo[i] + hi[i]) >> 1; }
            else { hi[i] = mid[i]; mid[i] = (lo[i] + hi[i]) >> 1; }
        }
    }
    for (i = 0; i < 100; i++) ans[i] = lo[i];
}
int binary_search(const unsigned *a, int n, unsigned x)
{
    int i;
    if (!done) {
        done = 1;
        for (i = 0; i < 100; i++) xs[i] = a[n + i];
        solve(a, n);
    }
    return ans[cnt++];
}

评测结果